Hoare quicksort in c

Question

Similarly to other users I am using this wikipedia algorithm. However I have tried to reimplement the algorithm using pointer arithmetic. However I'm having difficulty finding where I've gone wrong.

I think that this if statement is probably the cause but I'm not be sure.

...  
if (left >= right) {  
ret = (right - ptr);  
return ret;  
}  
temp = *left;
*left = *right;
*right = temp;

/* sortstuff.h */

extern void quicksort(const size_t n, int * ptr);

/* sortstuff.c */ 
size_t quicksortpartition(const size_t n, int * ptr);

void quicksort(const size_t n, int * ptr) {
    int* end = ptr + n - 1;

    // for debug purposes
    if (original_ptr == NULL) {
        original_ptr = ptr;
        original_count = n;
    }

    if (n > 1) {
        size_t index = quicksortpartition(n, ptr);
        quicksort(index, ptr);
        quicksort(n - index - 1, ptr + index + 1);
    }
    return;
}

size_t quicksortpartition(const size_t n, int * ptr) {
    int* right = ptr + n - 1;
    int* pivot = ptr + (n - 1) / 2;
    int* left = ptr;
    int temp;
    size_t ret = NULL;

    while (1) {
        while (*left <= *pivot && left < pivot) {
            ++left;
        }
        while (*right > *pivot) {
            --right;
        }
        if (left >= right) {
            ret = (right - ptr);
            return ret;
        }
        temp = *left;
        *left = *right;
        *right = temp;
        //print_arr();
    }
}

int main(void) {

}

/* main.c */ 

int array0[] = {5, 22, 16, 3, 1, 14, 9, 5};
const size_t array0_count = sizeof(array0) / sizeof(array0[0]);

int main(void) {
    quicksort(array0_count, array0);

    printf("array out: ");
    for (size_t i = 0; i != array0_count; ++i) {
        printf("%d ", array0[i]);
    }
    puts("");
}

I don't think there are any off by one errors

https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ and https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb and https://stackoverflow.com/questions/59097696/tricks-to-analyse-pointer-and-pointer-to-pointer-structures-in-c/59097858#59097858 can help you with narrowing problems down. — Yunnosch, Feb 11 '20 at 06:33

John Bollinger · Accepted Answer · 2020-02-11T07:23:32.210

The code you have presented does not accurately implement the algorithm you referenced. Consider in particular this loop:

        while (*left <= *pivot && left < pivot) {
            ++left;
        }

The corresponding loop in the algorithm description has no analog of the left < pivot loop-exit criterion, and its analog of *left <= *pivot uses strict less-than (<), not (<=).

It's easy to see that the former discrepancy must constitute an implementation error. The final sorted position of the pivot is where the left and right pointers meet, but the condition prevents the left pointer ever from advancing past the initial position of the pivot. Thus, if the correct position is rightward of the initial position then the partition function certainly cannot return the correct value. It takes a more thoughtful analysis to realize that in fact, the partition function is moreover prone to looping infinitely in that case, though I think that's somewhat data-dependent.

The latter discrepancy constitutes a provisional error. It risks overrunning the end of the array in the event that the selected pivot value happens to be the largest value in the array, but that's based in part on the fact that the left < pivot condition is erroneous and must be removed. You could replace the latter with left < right to resolve that issue, but although you could form a working sort that way, it probably would not be an improvement on the logic details presented in the algorithm description.

Note, however, that with the <= variation, either quicksortpartition() needs to do extra work (not presently provided for) to ensure that the pivot value ends up at the computed pivot position, or else the quicksort function needs to give up its assumption that that will happen. The former is more practical, supposing you want your sort to be robust.

score 0 · Answer 2 · answered Feb 11 '20 at 20:26

Pivot needs to be an int, not a pointer. Also to more closely follow the Wiki algorithm, the parameters should be two pointers, not a count and a pointer. I moved the partition logic into the quick sort function.

void QuickSort(int *lo, int *hi)
{
int *i, *j;
int p, t;
    if(lo >= hi)
        return;
    p = *(lo + (hi-lo)/2);
    i = lo - 1;
    j = hi + 1;
    while (1){
        while (*(++i) < p);
        while (*(--j) > p);
            if (i >= j)
                break;
            t = *i;
            *i = *j;
            *j = t;
    }
    QuickSort(lo, j);
    QuickSort(j+1, hi);
}

The call would be:

    QuickSort(array0, array0+array0_count-1);

Hoare quicksort in c

2 Answers2