Quicksort segmentation fault

I implemented a quicksort algorithm in C and works properly in vectors with less that 30000 elements. But, it's get a segmentation fault in line

swap(&vet[sup], &vet[(sup-inf+1)/2]);

with bigger vectors. This is the full algorithm:

void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
} 
int partition(int inf, int sup, int vet[]){
    while (inf<sup){
        while (vet[inf]<=vet[sup] && inf<sup){inf++;}
        while (vet[inf]<=vet[sup] && inf<sup){sup--;}
        if (inf<sup){swap(&vet[inf], &vet[sup]);}
    }
    return inf;
}
void median (int inf, int sup, int vet[]){ //select the median of the first, last and midle value of the vector
    if (vet[inf]>vet[(sup-inf+1)/2])
        swap(&vet[inf], &vet[(sup-inf+1/2)]);
    if (vet[sup]>vet[(sup-inf+1)/2])
        swap(&vet[sup], &vet[(sup-inf+1)/2]);  
    else if (vet[sup]<vet[inf])
        swap(&vet[sup], &vet[inf]);    
}
void quicksort(int inf, int sup, int vet[]){
    if (inf<sup){
        median(inf, sup, vet);    
        int piv=partition(inf, sup, vet);
        quicksort(inf, piv-1, vet);
        quicksort(piv+1, sup, vet);
    }
}

I'm tried to write the quicksort which the minimal declaration of variables as possible, but it still getting a segmentation fault. I'm don't know if it's a stack overflow or is a problem with the pointer that only happens with bigger vectors.

Sorry for my bad English, I'm still learning

Solution

There are multiple problems in your code:

your coding style is hard to read and debug: for example cramming the test and the swapping code on the same line makes it impossible to tell which part causes the crash. Write a single statement per line and break control statements on multiple lines.
the swapping code xor trick is obsolete: it is cryptic, potentially undefined and inefficient, Worse even: it does not work if a and b point to the same location. Use the simpler code:
```
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
```

the partition code is incorrect: you must save the initial value of sup so all comparisons are performed with the pivot value and you must swap the pivot to the final inf index:

int partition(int inf, int sup, int vet[]) {
    int pivot = sup;
    while (inf < sup) {
        while (vet[inf] <= vet[pivot] && inf < sup) {
            inf++;
        }
        while (vet[sup] >= vet[pivot] && inf < sup) {
            sup--;
        }
        swap(&vet[inf], &vet[sup]);
    }
    swap(&vet[inf], &vet[pivot]);
    return inf;
}

it is possible, although unlikely that the dataset provided to your code be crafted to cause a stack overflow. You might want to study the classic article by Doug McIlroy: A killer adversary to QuickSort that explains how to construct such a vector. A simple counter measure that prevents potential stack overflow but does not reduce the quadratic time complexity is easy to implement: only recurse on the smaller half and loop on the larger half.
a more likely the reason for the crash is you do not select the middle element in the slice with sup/2+1, you should write (inf + (sup - inf + 1) / 2, hence the pivot is not correctly selected so the algorithm may recurse too many times even for a random vector.

Here is a modified version:

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

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

int partition(int inf, int sup, int vet[]) {
    int pivot = sup;
    while (inf < sup) {
        while (vet[inf] <= vet[pivot] && inf < sup) {
            inf++;
        }
        while (vet[sup] >= vet[pivot] && inf < sup) {
            sup--;
        }
        swap(&vet[inf], &vet[sup]);
    }
    swap(&vet[inf], &vet[pivot]);
    return inf;
}

// Select the median of the first, last and middle value of the vector
// and move it to vet[sup]
void median(int inf, int sup, int vet[]) {
    int m = inf + (sup - inf + 1) / 2;
    // set vet[m] = min(vet[inf], vet[m])
    if (vet[inf] > vet[m]) {
        swap(&vet[inf], &vet[m]);
    }
    if (vet[sup] > vet[m]) {
        // set vet[sup] = min(vet[sup], min(vet[m], vet[inf]))
        swap(&vet[sup], &vet[m]);
    } else
    if (vet[sup] < vet[inf]) {
        // set vet[sup] = min(vet[sup], max(vet[m], vet[inf]))
        swap(&vet[sup], &vet[inf]);
    }    
}

void quicksort(int inf, int sup, int vet[]) {
    while (inf < sup) {
        median(inf, sup, vet);    
        int piv = partition(inf, sup, vet);
        // recurse on the smaller half, loop on the other half
        if (piv - inf < sup - piv) {
            quicksort(inf, piv - 1, vet);
            inf = piv + 1;
        } else {
            quicksort(piv + 1, sup, vet);
            sup = piv - 1;
        }
    }
}

int main(int argc, char *argv[]) {
    size_t n = argc < 2 ? 30000 : strtol(argv[1], NULL, 0);
    int *array = calloc(n, sizeof(*array));
    int res = 0;

    if (array == NULL) {
        fprintf(stderr, "cannot allocate memory for %zu elements\n", n);
        return 1;
    }

    srand(time(NULL));
    for (size_t i = 0; i < n; i++) {
        array[i] = rand();
    }

    quicksort(0, n - 1, array);
    for (size_t i = 1; i < n; i++) {
        if (array[i] < array[i - 1]) {
            printf("sort error at %zu: %d > %d\n",
                   i, array[i - 1], array[i]);
            res = 1;
            break;
        }
    }
    free(array);
    return res;
}