Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!

# recursive quick sort issues

jeol petorz
Greenhorn
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
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
Posts: 24212
35
java.util.Arrays.sort() works awfully nice too -- unless this is homework.