Why does this Quicksort work?

I find this Quicksort partitioning approach confusing and wrong, yet it seems to work. I am referring to this pseudocode. Note: they also have a C implementation at the end of the article, but it's very different from their pseudocode, so I don't care about that.

I have also written it in C like this, trying to stay true to the pseudocode as much as possible, even if that means doing some weird C stuff:

#include <stdio.h>

int partition(int a[], int p, int r)
{
    int x = a[p];

    int i = p - 1;
    int j = r + 1;

    while (1)
    {
        do
            j = j - 1;
        while (!(a[j] <= x));

        do开发者_C百科
             i = i + 1;
        while (!(a[i] >= x));

        if (i < j)
        {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        else
        {
            for (i = 1; i <= a[0]; ++i)
                printf("%d ", a[i]);
            printf("- %d\n", j);

            return j;
        }
    }
}


int main()
{
    int a[100] = //{8, 6,10,13,15,8,3,2,12};
                {7, 7, 6, 2, 3, 8, 4, 1};

    partition(a, 1, a[0]);
    return 0;
}

If you run this, you'll get the following output:

1 6 2 3 4 8 7 - 5

However, this is wrong, isn't it? Clearly a[5] does not have all the values before it lower than it, since a[2] = 6 > a[5] = 4. Not to mention that 7 is supposed to be the pivot (the initial a[p]) and yet its position is both incorrect and lost.

The following partition algorithm is taken from wikipedia:

int partition2(int a[], int p, int r)
{
    int x = a[r];
    int store = p;

    for (int i = p; i < r; ++i)
    {
        if (a[i] <= x)
        {
            int t = a[i];
            a[i] = a[store];
            a[store] = t;

            ++store;
        }
    }

    int t = a[r];
    a[r] = a[store];
    a[store] = t;

    for (int i = 1; i <= a[0]; ++i)
        printf("%d ", a[i]);
    printf("- %d\n", store);

    return store;
}

And produces this output:

1 6 2 3 8 4 7 - 1

Which is a correct result in my opinion: the pivot (a[r] = a[7]) has reached its final position.

However, if I use the initial partitioning function in the following algorithm:

void Quicksort(int a[], int p, int r)
{
    if (p < r)
    {
        int q = partition(a, p, r); // initial partitioning function

        Quicksort(a, p, q);
        Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r.
    }
}

... it seems to be a correct sorting algorithm. I tested it out on a lot of random inputs, including all 0-1 arrays of length 20.

I have also tried using this partition function for a selection algorithm, in which it failed to produce correct results. It seems to work and it's even very fast as part of the quicksort algorithm however.

So my questions are:

1. Can anyone post an example on which the algorithm DOESN'T work?
2. If not, why does it work, since the partitioning part seems to be wrong? Is this another partitioning approach that I don't know about?

I think the partitioning is correct. 7 is the pivot. The original array is partitioned into a sub array of length 5 containing elements less than or equal to 7 and a sub array of length 2, containing elements greater or equal to 7.

Extending on from above here is what it should look like

void swap(int *a, int *b)
{
    int x;

    x = *a;
    *a = *b;
    *b = x;
}

int partition(int s[], int l, int h) 
{ 
    int i;
    int p;/* pivot element index */ 
    int firsthigh;/* divider position for pivot element */ 

    p = h; 
    firsthigh = l; 
    for (i = l; i < h; i++) 
        if(s[i] < s[p]) { 
            swap(&s[i], &s[firsthigh]); 
            firsthigh++; 
        } 
    swap(&s[p], &s[firsthigh]); 

    return(firsthigh); 
}

void quicksort(int s[], int l, int h)
{
    int p;/* index of partition */ 
    if ((h - l) > 0) {
        p = partition(s, l, h); 
        quicksort(s, l, p - 1); 
        quicksort(s, p + 1, h); 
    } 
}

int main()     
{         
    int a[100] = //{8, 6,10,13,15,8,3,2,12};  
                   {7, 7, 6, 2, 3, 8, 4, 1};              
    quicksort(a, 0, 7);
    return 0; 
}    

From Wikipedia (I've emphasized the part that I think addresses your question directly):

This is the in-place partition algorithm. It partitions the portion of the array between indexes left and right, inclusively, by moving all elements less than or equal to array[pivotIndex] to the beginning of the subarray, leaving all the greater elements following them. In the process it also finds the final position for the pivot element, which it returns. It temporarily moves the pivot element to the end of the subarray, so that it doesn't get in the way. Because it only uses exchanges, the final list has the same elements as the original list. Notice that an element may be exchanged multiple times before reaching its final place. It should also be noted that in case of pivot duplicates in the input array, they can be spread across left subarray, possibly in random order. This doesn't represent a partitioning failure, as further sorting will reposition and finally "glue" them together.

Could that be what you were missing?

You are getting confused between the index of the item and the iten value

Look at your header

int partition(int a[], int p, int r) ;

Now if we changed the data type on the array a to some weird data type you will see the problem

int partition( Otherdatatype a[], int p, int r) ;

You call the function from within your main with

partition(a, 1, a[0]);

See the problem a[0] is the value of the entry in a[0] not an index value.

Imagine a[0] had the value 200 in your code simply change the first item value to 200 and you will get a runtime error "attempt to access memory out of range" because if you follow thru a[0] = 200 that is passed into partition as value r then follow what happens inside partition.

The thing to remember is this is a sort routine in your partition header the list in array a may not be of the same type as the indexes .. p and r of your header are clearly indexes referring to an index position and a is the list to be sorted.

Thus your main start to a sort is

partition(a, 0, items_in_array-1);

Do you see why? Array a runs from a[0] ... a[items_in_array-1]

So in your sample above you have preloaded 8 values into your array so your partition call from main should be

partition(a, 0, 7);