Ошибка сегментации быстрой сортировки

В вашем коде есть несколько проблем:

• ваш стиль кодирования трудно читать и отлаживать: например, если втиснуть тест и код замены в одну строку, невозможно определить, какая часть вызывает сбой. Пишите по одному оператору в строке и разбивайте управляющие операторы на несколько строк.

• трюк с xor подстановки кода устарел: он загадочный, потенциально неопределенный и неэффективный. Хуже того: он не работает, если a и b указывают на одно и то же место. Используйте более простой код:

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

• код раздела неверен: необходимо сохранить начальное значение sup, чтобы все сравнения выполнялись со значением опорной точки, и вам необходимо заменить опорную точку на окончательный индекс inf:

  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;
  }
  

• это возможно, хотя и маловероятно, что набор данных, предоставленный вашему коду, будет создан так, чтобы вызвать переполнение стека. Возможно, вам захочется изучить классическую статью Дуга Макилроя: убийственный противник быстрой сортировки, в которой объясняется, как построить такой вектор. Простую контрмеру, которая предотвращает потенциальное переполнение стека, но не уменьшает квадратичную временную сложность, легко реализовать: рекурсия только на меньшей половине и цикл на большей половине.

• более вероятная причина сбоя в том, что вы не выбираете средний элемент в срезе с помощью sup/2+1, вам следует написать (inf + (sup - inf + 1) / 2, следовательно, опорная точка выбрана неправильно, поэтому алгоритм может рекурсировать слишком много раз даже для случайного вектора.

Вот модифицированная версия:

#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;
}