QuickSort C implementation not working as expected

I am trying to implement the QuickSort algorithm in C, however it’s giving me a pretty hard time, I don’t know what I’m doing wrong but sometimes the output isn’t what I expected it to be:

#include <stdio.h>
#include <stdlib.h>

void printArray(int array[], int size){
    for(int i=0;i<size;i++) printf("%d ",array[i]);
    printf("\n");
}

void swap(int *a, int *b){
    int aux;
    aux = *a;
    *a=*b;
    *b=aux;
}


int partition(int array[], int l, int r, int size){
    int pivot_index = (l+r)/2;
    int pivot=array[pivot_index];
    while(l<r){
        while(l<size && pivot>=array[l]) l++;
        while(r>=0 && pivot<array[r]) r--;
        if(l<r) swap(&array[l],&array[r]);
    }
    swap(&array[pivot_index],&array[r]);
    return r;
}

void quickSort(int array[],int start,int end, int size){
    int pivot;
    if (end>start){
        pivot=partition(array,start,end,size);
        quickSort(array,start,pivot-1,size);
        quickSort(array,pivot+1,end,size);
    }
}

int main(){
    int array_test[]={948,4,0,89,7,34,1,3};
    printArray(array_test,(sizeof(array_test)/sizeof(array_test[0])));
    quickSort(array_test,0,(sizeof(array_test)/sizeof(array_test[0]))-1,(sizeof(array_test)/sizeof(array_test[0])));
    printArray(array_test,(sizeof(array_test)/sizeof(array_test[0])));
    return 0;
}

Input array/Output array:

948 4 0 89 7 34 1 3 -> 3 1 4 0 7 34 89 948

9 8 7 6 5 4 3 2 1 0 -> 0 1 2 4 3 5 6 7 8 9

9 8 7 59 6 5 4 6 3 0 2 1 0 -> 0 0 1 2 3 5 4 6 6 9 7 8 59

954 485 0 345 1 36 -> 954 36 0 1 345 485

As you can see, some arrays are giving me some pretty weird results, and I don’t really know why, so I’d appreciate if someone could help me figure it out.

>Solution :

Your main error is here

quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) , (sizeof(array_test) / sizeof(array_test[0])));

you are passing the same value for size and end. you need

quickSort(array_test, 0, (sizeof(array_test) / sizeof(array_test[0])) - 1 , (sizeof(array_test) / sizeof(array_test[0])));

Also when doing lots of index juggling like that you can do

int partition(int array[], int l, int r, int size) {
    assert(r > -1 && r < size);
    assert(l > -1 && l < size);

this will stop instantly in your debugger if you use an invalid index. This would have found your error

Leave a Reply