Thread: no one is able to explain!

qsort -> please explain-it

I started my discussion in the above link, while copy and pasting the Quicksort Algorithm from "The C Programming Language, Second Edition" by Brian W. Kernighan and Dennis M. Ritchie (page 87).

And I rised a simple question, e.g. if we have these inputs: e.g. {11, 3, 9, 7, 4)

How this algorithm will work (just one iteration)! Believe me or not, no one was able to explain it

TERRIFYING! And I still have problem to understand it... well I am novice, dummy etc. But what about others?

Code:

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left; /* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* restore partition elem */
qsort(v, left, last-1);
qsort(v, last+1, right);
}

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}

Are you even still paying attention to that thread?

Quick sort sorts through something called partitioning.

Explaining partitioning: You pick an element to partition around called the pivot (or last, in your code). In your code, the algorithm is going to pick the middle one every time. Then you swap the middle and first arguments. Then you walk the array comparing the ith element with the left element, and swapping to arrange it such that everything to the left of 'last' is less than 'left', and everything greater is to the right. This sorts the pivot into its final position, last, which explains the swap at the end.

With one element sorted, you still have to divide the array into two parts and partition each part. When every element has had a chance to be a pivot, the array is sorted.

Code:

( 9, 3, 11, 7, 4, ) pivot=0...
( 9, 3, 11, 7, 4, ) pivot=1...
( 9, 3, 7, 11, 4, ) pivot=2...
( 9, 3, 7, 4, 11, ) pivot=3...
( 4, 3, 7, 9, 11, ) pivot=3...
( 3, 4, 7, ) pivot=0...
( 3, 4, 7, ) pivot=0...
( 4, 7, ) pivot=1...
( 4, 7, ) pivot=1...

You could have done this yourself, you know.