recursive quick sort issues

[jeol petorz]

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

public static String[] quickSort (String[] A, int start, int end){
 

        //if size is 1 return
        if (A.length < 2 ) return A;
 
        int pivotIndex = start;
 
            //do the partition
            for (int i=pivotIndex+1; i<end; i++){
 
                if (compareStrings(A[i],A[pivotIndex])){
 
                    swapString(A, pivotIndex+1, i);
                    swapString(A, pivotIndex, pivotIndex+1);
                    pivotIndex++;
 
                 }
 
            }
         return A;
 
    }   

[R Jarman]

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]

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