aspose file tools*
The moose likes Java in General and the fly likes recursive quick sort issues Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "recursive quick sort issues" Watch "recursive quick sort issues" New topic
Author

recursive quick sort issues

jeol petorz
Greenhorn

Joined: Nov 04, 2006
Posts: 1
this is my version of quick sort, and it works as it is.
aka, picks a pivot element and arranges the rest array around it. But i cant seem to figure out the last few lines of the method to make it recursive and sort the entire thing for me. thanks for your help


R Jarman
Greenhorn

Joined: Feb 08, 2005
Posts: 27
I attached a quicksort I use. Part of your problem is the "2" at the beginning. This should be different everytime it is called. My quicksort is something I found on the internet and modified for my use. I sort an arraylist of objects and instead of checking the value in the array, I check a value in the object in the array. That's what my getDeliveryDate() method calls are. Hope this helps.

private void quickSort(ArrayList<Bid> elements, int lowIndex, int highIndex)
{
int lowToHighIndex;
int highToLowIndex;
int pivotIndex;
int pivotValue;
Bid lowToHighValue;
Bid highToLowValue;
Bid parking;
int newLowIndex;
int newHighIndex;
int compareResult;

lowToHighIndex = lowIndex;
highToLowIndex = highIndex;

/** Choose a pivot, remember it's value
* No special action for the pivot element itself.
* It will be treated just like any other element.
*/

pivotIndex = (lowToHighIndex + highToLowIndex) / 2;
pivotValue = elements.get(pivotIndex).getDeliveryDate();

/** Split the Vector in two parts.
*
* The lower part will be lowIndex - newHighIndex,
* containing elements <= pivot Value
*
* The higher part will be newLowIndex - highIndex,
* containting elements >= pivot Value
*/

newLowIndex = highIndex + 1;
newHighIndex = lowIndex - 1;

// loop until low meets high
while ((newHighIndex + 1) < newLowIndex) // loop until partition complete
{
// loop from low to high to find a candidate for swapping
lowToHighValue = elements.get(lowToHighIndex);
while (lowToHighIndex < newLowIndex && lowToHighValue.getDeliveryDate() < pivotValue )
{
newHighIndex = lowToHighIndex; // add element to lower part
lowToHighIndex++;
lowToHighValue = elements.get(lowToHighIndex);
}

// loop from high to low find other candidate for swapping
highToLowValue = elements.get(highToLowIndex);

while (newHighIndex <= highToLowIndex && highToLowValue.getDeliveryDate() > pivotValue)
{
newLowIndex = highToLowIndex; // add element to higher part
highToLowIndex--;
highToLowValue = elements.get (highToLowIndex);
}

// swap if needed
if (lowToHighIndex == highToLowIndex) // one last element, may go in either part
{
newHighIndex = lowToHighIndex; // move element arbitrary to lower part
}
else if (lowToHighIndex < highToLowIndex) // not last element yet
{
if (lowToHighValue.getDeliveryDate() >= highToLowValue.getDeliveryDate()) // low >= high, swap, even if equal
{
parking = lowToHighValue;
elements.set (lowToHighIndex, highToLowValue);
elements.set (highToLowIndex, parking);

newLowIndex = highToLowIndex;
newHighIndex = lowToHighIndex;

lowToHighIndex++;
highToLowIndex--;
}
}
}

// Continue recursion for parts that have more than one element
if (lowIndex < newHighIndex)
{
this.quickSort(elements, lowIndex, newHighIndex); // sort lower subpart
}
if (newLowIndex < highIndex)
{
this.quickSort(elements, newLowIndex, highIndex); // sort higher subpart
}
}
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24184
    
  34

java.util.Arrays.sort() works awfully nice too -- unless this is homework.


[Jess in Action][AskingGoodQuestions]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: recursive quick sort issues