user3574076 user3574076 - 3 days ago 4
Java Question

Sedgewick Quicksort not making total sense

I understand the concept of quicksort, and most of the implementations I have seen largely make sense to me. However the one by Robert Sedgewick does not, his implementation is along the lines of:

private void sort(int lo, int hi) {
if (hi <= lo) return;
int j = partition(lo, hi);
sort(lo, j-1);
sort(j+1, hi);
}

private int partition(int lo, int hi) {
int start = lo;
int partition = hi + 1;
int pivot = theArray[lo];
while (true) {

// left to right
while (less(theArray[++start], pivot))
if (start == hi) break;

// right to left
while (less(pivot, theArray[--partition]))
if (partition == lo) break;

// check if pointers cross
if (start >= partition) break;

exch(theArray, start, partition);
}

// place pivot at partition
exch(theArray, lo, partition);

return partition;
}

private boolean less(int v, int w) {
return v < w;
}

private void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}


I understand all of it except for the partition function. Particularly what happens in the
while(true)
portion

MBo MBo
Answer

Let's make some "brain debug"

int pivot = theArray[lo];
Fixes 1st element as pivot value

while (less(theArray[++start], pivot)) if (start == hi) break;
Finds the first element for exchange - the leftmost one bigger than pivot

while (less(pivot, theArray[--partition])) if (partition == lo) break;
Finds the second element for exchange - the rightmost one less than pivot

if (start >= partition) break;
Breaks while (true) loop when there is no more elements to exchange

exch(theArray, start, partition);
Exchanges elements found

Example [5 3 8 9 2]:
5 is pivot
first 'bad' element is 8
second one is 2
they are exchanged

[5 3 2 9 8]

now first index stops at 4 (hi), second index stops at 2, loop breaks, and 5 exchanges with 2.

Result: [2 3 5 9 8]
Subranges (2,3,5) and (9,8) are new partitions

Comments