Thread: A Few Questions About a Quicksort Algorithm Example

How does the split function know which elements "low" and "high" point to?

I don't know what you mean. Do you understand how functions and parameter passing works? It gets the values from the original call initially and then from the recursive calls.

In the split function, does the following assignment create a "hole" in the array

No, it doesn't really create a "hole". It does exactly what it says it does. It copies the value at that location to another variable. The value now exists in both places.

If you were to then print the value of element 0, what value would show on screen?

The same value it had before. Think about it.

Code:

int x = 1;   // The memory allocated to hold the value of x
             // now contains the value 1.
int y = x;   // The memory allocated to hold the value of y
             // now also contains the value 1.
             // x still contains the value 1, too.
             // y did not steal the value leaving x "empty".

Does this statement have the effect of moving the value pointed to by "high" to the hole spot pointed to by "low"?

Again, assignment statements don't "move" values. They copy them. And the way you've worded it seems like you're reading it backwards somehow. The value of a[low] is copied to a[high], then high is decremented.

The best way to learn and understand what's going on here is probably to step through the code in your debugger, watching the flow of execution and the changes in the array with each step.
Here's a bit of a primer on recursion which is a function that calls itself until a base case is met.
Here's another overview of the algorithm.

After the partitioning, the 12 ends up at index 4. The function then calls itself twice, first with low = 0, high = 3, then again with low = 5, high = 6. When it calls itself with low = 0, high = 3, the pivot value will be 10, which will end up at 3, and it calls itself again with low = 0, high = 2, then again with low = 3, high = 3 (nothing to do in this case). Creating a "hole" isn't needed. Take a look at Hoare partition scheme, which is faster, despite including the pivot value in either the left or right partition on the recursive calls:

Quicksort - Wikipedia

Thanks algorism, Hobbit and rcgldr. I'll answer each of you in a separate post.

Here's my response to algorism.

My lingering question is still around #1, but I better understand the other questions from your explanations.

Originally Posted by algorism

I don't know what you mean. Do you understand how functions and parameter passing works? It gets the values from the original call initially and then from the recursive calls.

Just for reading continuity, this question pertained to my GREEN marks.

I understand how function passing works. What I'm confused about is where in the code the split function gets the info on which elements should be considered "low" and "high."

To my understanding, this quicksort algorithm example is supposed to perform the "split" function before the "quicksort" function (recursion stuff). That comes from my reading of this program description that came a page earlier from the other excerpt I posted above. See blue annotations on this page for where I'M getting this idea in my head.



I just don't see a line in the "split" function that tells what elements are considered "low" and "high."

Is that green-colored call of "quicksort" sufficient to inform the entire program what the "low" and "high" elements are?

It's this one again, for clarity's sake

Code:

quicksort(a, 0, N - 1);

Originally Posted by algorism

No, it doesn't really create a "hole". It does exactly what it says it does. It copies the value at that location to another variable. The value now exists in both places.

Thanks, that helps! I understand this now

Originally Posted by algorism

The same value it had before. Think about it.

Code:

int x = 1;   // The memory allocated to hold the value of x
             // now contains the value 1.
int y = x;   // The memory allocated to hold the value of y
             // now also contains the value 1.
             // x still contains the value 1, too.
             // y did not steal the value leaving x "empty".

Understood on this too now. Thanks!

Originally Posted by algorism

Again, assignment statements don't "move" values. They copy them. And the way you've worded it seems like you're reading it backwards somehow. The value of a[low] is copied to a[high], then high is decremented.

I get this one too now!

Originally Posted by Hobbit

The best way to learn and understand what's going on here is probably to step through the code in your debugger, watching the flow of execution and the changes in the array with each step.

Thanks Hobbit. I'm going to do this later today

Changing the book statements to C based indexing which starts at 0:

sort elements 0 to i-1 by using quicksort recursively, sort elements i+1 to n-1 by using quicksort recursively

This should be clarified, quicksort just arranges a partition so that values less than pivot value are on the left, values greater than pivot value are on the right, and the pivot value is placed in it's final sorted location. Only when recursion results in a partition size of 1, 2, or 3, will that small partition end up sorted. At that point, all elements in that small partition will be in their final sorted locations. The array doesn't end up sorted until every recursion path has reached a point where partition size is reduced to 1, 2, or 3.

No the split function knows this because that is the information it was passed.

The split function takes an array and two ints denoting low and high.

The call to split in quicksort passes the array, an int representing low and an int representing high. Quicksort itself gets these values from main where it is called in the line quicksort( a, 0, N-1) so main tells quicksort to operate on array a with low set to zero and high set to N-1.

Next looking at the quicksort algorithm

Code:

void quicksort(int a[], int low, int high)
{
int middle;
 
if (low >= high) return;
middle = split(a, low, high);
quicksort(a, low, middle - 1);
quicksort(a, middle + 1, high);
}

First an int called middle is declared, then the base case is tested, the base case being that if low is greater than or equal to high then there's nothing more to do so we return. Low is zero, high is 6 ( N-1 N is 7) so we fail this test and so skip the return and go to partitioning. Next middle is set by the return value of the split function to which we pass the array a, the figure for low (0) and the figure for high (N-1 or 6). Now we know where the partition is it's at array index middle, so now we recursively sort each half of the array by calling the quicksort function again twice. The first call sorts the left half of the array from low to middle-1, the second call sorts the right hand side of the array from middle+1 to high. During each of these calls if the array isn't sorted then split is called again to decide a new partitioning element.

As I said, step through the code in the debugger. Watch the changes in the array as elements get swapped about. Watch how low, high and middle change during each call to quicksort.

Functions don't peek into other functions, they simply operate on the data that gets passed as parameters ( or sometimes global variables which can be accessed from anywhere) and either do something then return a value, or just do something returning nothing( a function returning void - other languages sometimes call these procedures).