Quicksort не работает с отсортированным массивом

Question

Я делаю проект для сравнения алгоритмов Bubblesort и Quicksort. Все работает нормально, пока я не хочу отсортировать данные, которые уже были отсортированы с помощью метода Quicksort. Вылетает на больших массивах (50 КБ, 100 КБ).

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

        read();  // just creates an array with random integers
        quickSortDSC(0, length - 1); //Here is the problem! (works if commented)
        t1 = clock();
        quickSortASC(0, length - 1);
        t2 = clock();
        cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";

Полный код:

    #include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

long length = 1000;
const long max_length = 100000;

int list[max_length];

void read()
{
    ifstream fin("random.dat", ios::binary);
    for (long i = 0; i < length; i++)
    {
        fin.read((char*)&list[i], sizeof(int));
    }
    fin.close();
}

void bubbleSort()
{
    int temp;
    for(long i = 0; i < length; i++)
    {
        for(long j = 0; j < length-i-1; j++)
        {
            if (list[j] > list[j+1])
            {
                temp        = list[j];
                list[j]     = list[j+1];
                list[j+1]   = temp;
            }
        }
    }
}


long partitionASC(long left, long right)
{
    int pivot_element = list[left];
    int lb = left, ub = right;
    int temp;

    while (left < right)
    {
        while(list[left] <= pivot_element)
            left++;
        while(list[right] > pivot_element)
            right--;
        if (left < right)
        {
            temp        = list[left];
            list[left]  = list[right];
            list[right] = temp;
        }
    }
    list[lb] = list[right];
    list[right] = pivot_element;
    return right;
}

long partitionDSC(long left, long right)
{
    int pivot_element = list[left];
    int lb = left, ub = right;
    int temp;

    while (left < right)
    {
        while(list[left] >= pivot_element)
            left++;
        while(list[right] < pivot_element)
            right--;
        if (left < right)
        {
            temp        = list[left];
            list[left]  = list[right];
            list[right] = temp;
        }
    }
    list[lb] = list[right];
    list[right] = pivot_element;
    return right;
}
//ascending order
void quickSortASC(long left, long right)
{
    long pivot;
    if (left < right)
    {
        pivot = partitionASC(left, right);
        quickSortASC(left, pivot-1);
        quickSortASC(pivot+1, right);
    }
}

//descending order
void quickSortDSC(long left, long right)
{
    long pivot;
    if (left < right)
    {
        pivot = partitionDSC(left, right);
        quickSortDSC(left, pivot-1);
        quickSortDSC(pivot+1, right);
    }
}

int main()
{
    double t1, t2;

    for (length = 1000; length <= max_length; )
    {
        cout << "\nLength\t: " << length << '\n';

        read();
        t1 = clock();
        bubbleSort();
        t2 = clock();
        cout << "Bubble Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";


        read();
        quickSortDSC(0, length - 1); //Here is the problem!
        t1 = clock();
        quickSortASC(0, length - 1);
        t2 = clock();
        cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";

        if(length == max_length)
            break;

        switch (length)
        {
        case 1000 :
            length = 10000;
            break;
        case 10000 :
            length = 50000;
            break;
        case 50000 :
            length = 100000;
            break;
        }
    }

    return 0;
}

Answer 1

При выборе первого элемента массива в качестве шарнира, вы попали в QuickSort поведение наихудшего, когда массив уже отсортирован. Таким образом, вы получаете поведение O (n ² ) (и, что еще хуже, пространство стека O (n), что, вероятно, приводит к переполнению стека).

Чтобы избежать этого, выберите другую опору. Обычно в качестве оси можно выбрать средний элемент:

int pivot_element = list[(left+right)/2];

или случайный элемент:

int pivot_element = list[left + random()%(right+1-left)];