Two Laptop Bag
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

recursive quick sort issues

jeol petorz

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

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
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
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;


// 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

Joined: Jul 08, 2003
Posts: 24199

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

[Jess in Action][AskingGoodQuestions]
I agree. Here's the link:
subject: recursive quick sort issues
It's not a secret anymore!