I'm reading The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie. I've reached chapter 5.6, where he explains the shell sort function using pointers to pointers.

I'm not getting, in the code example he gives, how the qsort function works: from what I understood, last will be equal to i?? Are we here swapping the same cell?? It's not making a sense for me.

Here's the code for the two functions:

/* qsort: sort v[left]...V[right] into increasing order */
void qSort(void *v[], int left, int right, funcP comp)
{
    int i, last;

    void swap(void *v[], int, int);

    if (left >= right)             /* do nothing if array contains */
        return;                    /* fewer than two elements */
    swap(v, left, (left   right) / 2);
    last = left;
    for (i = left   1; i <= right; i  )
        if ((*comp)(v[i], v[left]) < 0)
            swap(v,   last, i);
    swap(v, left, last);
    qSort(v, left, last - 1, comp);
    qSort(v, last   1, right, comp);
}

}

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

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}```

CodePudding user response：

I'm reading The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie. I've reached chapter 5.6, where he explains the shell sort function using pointers to pointers.

Note that the code presented in the question implements the Quicksort algorithm, not Shell sort.

I'm not getting, in the code example he gives, how the qsort function works: from what I understood, last will be equal to i?? Are we here swapping the same cell?? It's not making a sense for me.

It may be that last is equal to i. In that case, the swap has no net effect. But the first time the comparison function returns a result that is greater than or equal to 0, i will increase without last increasing (take note of the if statement), so that i is equal to last 2. For the rest of that execution of qsort, i will be at least that far in advance of last, so that last is not equal to i. For random data, there will typically be many such events, so that i continues to get farther and farther ahead of last.

Overall, the function rearranges the given array elements into two groups, with all the elements of one less than or equal to all the elements of the other. Then it recurses to do the same job on each of the two groups it just formed.

CodePudding user response：

YES it may move a value to itself.

NO last is not equal to i.

qsort AKA quicksort - there are many versions on the web. Go back to K&R chapter 4's version first, the 5.6 version is just to demonstrate pointers. Replace the word "last" with "pivot" then take a peek at the wiki - google search "quick sort".

ALGOLRYTHM, generalized -

select a pivot value, save it somewhere
now classify the rest of the partition as high or low
restore the pivot value to be between the list of lows and the list of highs

example ?=unknown L=low H=high P=pivot

???????? to start
???P???? select Pivot value
P??????? swap the pivot value with the initial value: i.e. save it
LP?????? or PH?????? next step
several repeats
PHHHHHHH or LLLLLLLP or something like LLLPHHHH 
finally
some versions LLLLHHHP
some versions PLLLLHHH
a few         LLLPLHHH
the last step swaps the last low or high with the Pivot
so            PLLLLHHH, after swap LLLLPHHH
or            LLLLHHHP, after swap LLLLPHHH
or            LLLPLHHH, after swap LLLLPHHH
exact detail depends on version

Always P winds up in it's final position. recursing to solve two new partitions LLLL and HHH.

This is why I think of qsort as classification sort, since it simply classifies all values in a partition as high or low relative to the selected pivot. Qsort is a poor choice for large sorts, as it can go Quadratic (aprox 1/2(N^2)) but is usually faster than (N log N) time. Note also that most versions of qsort are unstable on duplicate keys.