As with my other questions, this one deals with an example from KN King's introductory text on C.
I have gotten to the chapter on functions, and am trying to better understand the Quicksort algorithm example he gives before I move on.
I am trying to reconcile some of the pseudocode he provides with the C code he provides. I'm having difficulty matching up the natural language descriptions in the pseudocode with some unfamiliar C code lines that I spotted. It's a good textbook, but I find it's not explicit enough for me sometimes.
Here are the questions I have. I have color coded the questions with what I'm looking at in the pseudocode and the C code provided below.
Many thanks in advance!
1). GREEN How does the split function know which elements "low" and "high" point to? The only relevant part of the program I can find is in the main section, which contains a line that passes through 0 as "low" and N-1 as "high."
Code:
quicksort(a, 0, N - 1);
But isn't this a function call of quicksort? How can this possibly get the right info on "low" and "high" to the split function? I am new to C, so take it easy on me. I know I must be missing some basic idea here.
2). ORANGE In the split function, does the following assignment create a "hole" in the array at element 0? Does it also move the element to the side as show in the pseudocode picture?
Code:
int part_element = a[low];
3). Related to question #2. If you were to then print the value of element 0, what value would show on screen? Since there's nothing there would you see an error?
4). RED Related to questions #2 and #3, if there's a hole in low, how would you evaluate this statement?
Code:
a[low] <= part_element
5). BLUE Does this statement have the effect of moving the value pointed to by "high" to the hole spot pointed to by "low"?
Code:
a[high--] = a[low];
Code:
#include <stdio.h>
#define N 7
/* FUNCTION PROTOTYPES */
void quicksort(int a[], int low, int high);
int split(int a[], int low, int high);
/* MAIN */
main()
{
int a[N], i;
printf("Enter %d numbers to be sorted: ", N);
for (i = 0; i < N; i++)
scanf_s("%d", &a[i]);
quicksort(a, 0, N - 1);
printf("In sorted order: ");
for (i = 0; i < N; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
/* SPLIT FUNCTION */
int split(int a[], int low, int high)
{
int part_element = a[low];
for (;;) {
while (low < high && part_element <= a[high])
high--;
if (low >= high)
break;
a[low++] = a[high];
while (low < high && a[low] <= part_element)
low++;
if (low >= high)
break;
a[high--] = a[low];
}
a[high] = part_element;
return high;
}
/* QUICKSORT FUNCTION */
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);
}
Pseudocode: