K&R Quicksort issue

Question

I seem to be having a problem understanding where the issue is in the qsort implementation by K&R (C Programming Language second edition).

void qsort_1(int v[], int left, int right)
{
    int i, last;

    void swap(int v[], int i, int j);

    if (left >= right) 
            return;
    swap(v, left, (left + right)/2);
    last = left;                    
    for (i = left + 1; i <= right; i++)
            if (v[i] < v[left])
                    swap(v, ++last, i);
    swap(v, left, last);
    qsort_1(v, left, last-1);
    qsort_1(v, last+1, right);
}

This is their version, I only renamed it to qsort_1 so that I could use the built in one at the same time.

int arr_len = 9;

int main() {
int a[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };
int b[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };

    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    putchar('\n'); // space
    
    qsort(b, arr_len, sizeof(int), cmpfunc); // sort second array with standard qsort
    qsort_1(a, 0, arr_len); // sort first array with K&R qsort
    
    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    
    return 0;

}

print_a is a mini function for displaying an array, just one for loop. qsort is the official standard implementation.

The output I get is:

gcc -O2 -lm -o qsort qsort.c
5 5 4 6 3 7 8 13 17
5 5 4 6 3 7 8 13 17

0 3 4 5 5 6 7 8 13
3 4 5 5 6 7 8 13 17

There seems to be a leading 0 and the last element is removed in the K&R qsort everytime. ...Help

void print_a(int a[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

If needed, here are the cmpfunc and print_a.

Tried googling the problem but no one seemed to have the same issue.

EDIT: The code changed in the main function:

int main() {
    int a[] = { 5 , 5 ,4 ,6 ,3 ,7 ,8, 13, 17 };
    int b[] = { 5 , 5 ,4 ,6 ,3 ,7 ,8, 13, 17 };

    print_a(a, arr_len);
    print_a(b, arr_len);
    putchar('\n');

    qsort(b, arr_len, sizeof(int), cmpfunc);
    qsort_1(a, 0, **arr_len - 1**);

    print_a(a, arr_len);
    print_a(b, arr_len);

    return 0;
}

Answer 1

When in doubt, look at the code you wrote.

• We can assume for a moment that K&R knew what they were doing.
• We can further assume that the authors of qsort in the standard library knew what they were doing as well.

Therefore, the first places we should look at what you authored. So what did you really author. The print function, the qsort comparator, and basically everything in main. A quick review reveals:

• print_a is certainly ok, provided the base address and length are valid (and they are in this usage case), so that's out.
• The qsort comparator seems correct, since (a) it works, and (b) it has nothing to do with questionable output from a totally unrelated function, qsort_1. So that's out.

That leaves only main. Within that function we have:

int main() 
{
    int a[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };
    int b[] = { 5, 5, 4, 6, 3, 7, 8, 13, 17 };

    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    putchar('\n'); // space
    
    qsort(b, arr_len, sizeof(int), cmpfunc); // sort second array with standard qsort
    qsort_1(a, 0, arr_len); // sort first array with K&R qsort
    
    print_a(a, arr_len); // print first array
    print_a(b, arr_len); // print second array
    
    return 0;

}

From this:

• The array declarations are certainly ok.
• The print_a calls check out ok (base address and length are valid).
• The call to qsort is unrelated, and obviously ok.

That leave only one line of code in this entire program that could be the culprit:

qsort_1(a, 0, arr_len); // sort first array with K&R qsort

Checking the algorithm, the K&R function expects:

• The array base address (ok)
• The first index in the partition to sort, in this case 0. (ok)
• The last index in the partition to sort. Um...

That's the problem. arr_len is not the last index. It is the length of the sequence. Since arrays in C are 0-index based, the last index is therefore arr_len-1, not arr_len.

Fix that:

qsort_1(a, 0, arr_len-1);

And the code will work as-expected.