nbpeth nbpeth - 17 days ago 6
Groovy Question

Quicksort Recursion

So I've successfully implemented a quicksort that uses the leftmost element as the pivot every time. I've been trying to implement quicksort using the middle element and having some complicated results. I have been working off of examples that has quicksort recursively call itself without wrapping the calls in any sort of condition and, as you might imagine, it gets stuck on the first call to itself.

The first calls to partition with the samples I've used partition the array correctly, then as it approaches the end, just swaps the two of the elements at the beginning over and over again.

The strategy that I am attempting is to pick the middle element from the list as the pivot, stow it away at the end of the array and then proceed to swap indices. After that pass it complete, I put the pivot between the partitioned arrays. Looks good after a couple of passes, but as I mentioned, gets stuck early on and never gets to the call that should sort the second partition.

any nudges would be greatly appreciated - I also was working in groovy, if you see anything off (and hopefully that isn't causing any issues, but I avoided duck typing for this

the original array is

[100, 305, 2, 2002, 18, 99, 211, 30, 50, 1000, 403, 4, 400, 77]


and when stack overflow is reached the array is

[2, 4, 18, 30, 50, 99, 77, 100, 211, 1000, 403, 305, 400, 2002]


class OtherQuickSort {

static void sort(int[] array){

quickSort(array, 0, array.length - 1)

}

static void quickSort(int[] array, int first, int last){
int pivotIndex = partition(array, first, last)

quickSort(array, first, pivotIndex - 1)
quickSort(array, pivotIndex, last)
}

static int partition(int[] array, int first, int last){
int pivotIndex = (first + last) / 2
int pivotValue = array[pivotIndex]

swapIndices(array, pivotIndex, last)

int indexFromRight = last - 1
int indexFromLeft = first

while(indexFromLeft <= indexFromRight){
while(array[indexFromLeft] < pivotValue){
indexFromLeft++
}
while(array[indexFromRight] > pivotValue){
indexFromRight--
}

if(indexFromLeft <= indexFromRight) {
swapIndices(array, indexFromLeft, indexFromRight)
indexFromLeft++
indexFromRight--
}
}

swapIndices(array, indexFromLeft, last)

indexFromLeft
}

static void swapIndices(int[] array, int left, int right){
int leftValue = array[left]
array[left] = array[right]
array[right] = leftValue
}
}

Answer

You need to update your quickSort method. Value at the pivotIndex is already in its sorted position so you need not pass it again.

static void quickSort(int[] array, int first, int last){
    if(last > first){
        int pivotIndex = partition(array, first, last);

        quickSort(array, first, pivotIndex-1);
        quickSort(array, pivotIndex+1, last);
    }
}