no one is able to explain!

http://cboard.cprogramming.com/c-pro...tml#post945120

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;
}

---

The idea is somewhat close to that of binary search, but here no part of an array should be ignored, that's why two statements of recursion are used. Try to trace this algorithm in debugger or even on plain paper.

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.

Quote:

---

Originally Posted by c_lady

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

---

Part of that was my fault for not interpreting the initial inputs correctly, but you need to take some responsibility too, because the reason I mis-interpreted them is that YOU did not provide the information.

If you want help with stuff like this, you have to use your brain and make an effort to provide the necessary information, and not expect others to deduce -- which might be why no one else even tried.

Code:

---

void qsort(int v[], int left, int right)

---

What should the initial values for "left" and "right" be here for array (11, 3, 9, 7, 4)? YOU have the book this code came from, it MUST explain that part. Anyway, I am sure if you go thru the process I did in the last thread, but use 0 and 4 instead of 0 and 3, it will work out. Try it on paper.* The -1 indicated a premature end to one side of the sort.

Also, it is kind of amazing that almost 24 hours later it has not occurred to you to TEST the code and include some simple printf() statements to help you follow the course of execution and how various values change (you could also do that with a debugger). This is a MANDATORY skill for programming, start today!!

* if it doesn't work out, post the attempt you made and I will go thru it again, promise. Oh but also you must post the information I mentioned. Perhaps maybe the exercise # too, a lot of K&R stuff is online. I think except for the random pivot value that is actually a pretty nice in-place qsort.