QuickSort не работает для больших входов

Question

Может кто-нибудь заметить проблему с моей быстрой реализацией сортировки ниже?Кажется, он не работает на массивах с более чем 10 элементами.

void swap(int *p1, int *p2)
{
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

void generateRandom(int arr[], int size)
{
    srand(time(NULL));
    int i;

    for (i = 0; i < size; i++)
    {
        arr[i] = rand() % 100;
    }
}

int partition(int arr[], int start, int end)
{
    int i = start, j = end;
    int pivot = arr[start];

    for (;;)
    {
        for (; arr[i] < pivot; i++);
        for (; arr[j] > pivot; j--);

        if (i < j)
        {
            swap(&arr[i], &arr[j]);
        }
        else
        {
            return j;
        }
    }
}

void quickSort(int arr[], int start, int end)
{
    int part;

    if (start < end)
    {
        part = partition(arr, start, end);
        quickSort(arr, start, part);
        quickSort(arr, part + 1, end);
    }
}

int main()
{
    generateRandom(arr, 100);
    for (i = 0; i < 100; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    quickSort(arr, 0, 99);
    for (i = 0; i < 100; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    return 0;
}

Answer 1

Во-первых, ваш код не компилируется.Когда я внес исправления для его компиляции (добавив stdio.h и определения для arr и i в main), он зациклился бесконечно, что он будет делать, если раздел начинается и заканчивается в центре.Вам нужно увеличивать и уменьшать до сравнений, а не после.Вы можете сделать это, начав с i = start-1 и j = end + 1 и изменив сначала свои внутренние циклы на увеличение или уменьшение, или вы можете оставить их как есть и просто сделать i ++ и j-- после перестановки -Я сделал это, и сортировка работает.

Обратите внимание, что ваш сводный выбор плох для уже отсортированных массивов;Вы действительно должны выбрать медиану из 3 или даже 9 значений.

PS Другие желательные оптимизации: 1) Переключитесь на сортировку вставки для небольших разделов - оптимальная точка отсечения зависит от машины.Другой подход состоит в том, чтобы не сортировать разделы ниже определенного размера, а затем выполнять сортировку вставкой по всему массиву после выполнения быстрой сортировки.Также возможно использовать heapsort вместо сортировки вставкой, если сделано тщательно;гугл интросорт.2) быстрая сортировка выполняет два рекурсивных вызова;устраните второй, установив start = part + 1 и зацикливание.3) Избегайте возможности переполнения стека, сначала быстро сортируя больший раздел.4) Исключите первый рекурсивный вызов, используя явный стек.5) Встроенный своп () и раздел ().6) Не беспокойтесь об этом и просто вызовите процедуру библиотеки qsort.: -)

Answer 2

У меня была такая же проблема, но я изменил цикл while на do..while, и он заработал.

Теперь это мой новый код.

int partition(int a[], int lo, int hi)  {
int v = a[lo], i = lo, j = hi;

do  {

    do  {
        i++;
    } while(a[i] < v) ;

    do  {
        j--;
    }while(a[j] > v) ;

    if(i < j)   interchange(&a[i], &a[j]);  

}while(i < j);

interchange(&a[lo], &a[j]);     
return j;
}