File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
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: 24187

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