Quicksort не может последовательно сортировать наборы данных по 100 000 целых чисел

Question

Я реализовал несколько вариантов алгоритма быстрой сортировки в C ++, но все они имеют большой недостаток.Им не удается отсортировать наборы данных из 100 000 целых чисел за разумное время.Иногда наборы данных из 10 000 целых чисел также терпят неудачу, но гораздо реже.Первоначально я подозревал, что причиной выбора был выбор точки разворота, но даже при случайном выборе разворота алгоритм не выполнялся в течение разумного периода времени.Может ли кто-нибудь помочь мне определить причину низкой производительности моей реализации Quicksort?

Ниже приведена моя реализация Quicksort с фиксированным поворотом.

void quicksort(std::vector<int> &list, int left, int right)
{
    if (left >= right)
       return;
    int pivot = list[left + (right - left) / 2];
    int oldPivot = partition(list, pivot, left, right);
    quicksort(list, left, oldPivot - 1);
    quicksort(list, oldPivot + 1, right);
}

// Hoare Partitioning Scheme
int partition(std::vector<int> &list, int pivot, int left, int right)
{
    while (true)
    {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        // Stop when the pivot is reached.
        if (left >= right)
            return left;
        std::swap(list[left], list[right]);
    }
}

Чтобы проверить алгоритм Quicksort для вектора100 000 неупорядоченных целых чисел Я использую следующий код:

std::vector<int> randomizeIntVector(int size)
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> rand_int(INT_MIN, INT_MAX);
    std::vector<int> vector;
    for (int i = 0; i < size; i++)
        vector.push_back(rand_int(rng));
    return vector;
}

int main()
{
    std::vector<int> vector = randomizeIntVector(100000);
    std::vector<int> expectedVector = vector;
    quicksort(vector, 0, vector.size() - 1);
    std::sort(expectedVector.begin(), expectedVector.end());
    assert(vector == expectedVector);
}

Код можно протестировать для различных векторных размеров здесь

Answer 1

Две проблемы в коде: во-первых, oldPivot - это индекс, а не сводное значение.Код использует его как значение.Измените это на index, чтобы устранить путаницу.

Во-вторых, вызовы быстрой сортировки продвигались по обе стороны от oldPivot, а не только в одну сторону.

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

#include <vector>
#include <list>
#include <random>
#include <algorithm>
#include <iostream>


void quicksort(std::vector<int> &list, int left, int right);
int partition(std::vector<int> &list, int pivot, int left, int right);
int randomize_pivot(int left, int right);
std::vector<int> randomizeIntVector(int size);

void print_vector(std::vector<int> v, int left, int right)
{
    for (int i = left; i <= right; i++) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}

void quicksort(std::vector<int> &list, int left, int right)
{

    if (left >= right)
        return;
    int pivot = list[left + (right - left) / 2];
    int index = partition(list, pivot, left, right);
    quicksort(list, left, index - 1);
    quicksort(list, index, right);  // prior was 'index + 1', which skipped a cell
}

// Hoare Partitioning Scheme
int partition(std::vector<int> &list, int pivot, int left, int right)
{
    while (left <= right) {
        while (list[left] < pivot)
            left++;
        while (list[right] > pivot)
            right--;
        if (left <= right) {
            std::swap(list[left], list[right]);
            left++;
            right--;
        }
    }
    return left;
}

std::vector<int> randomizeIntVector(int size)
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> rand_int(INT_MIN, INT_MAX);
    std::vector<int> vector;
    vector.reserve(size);
    for (int i = 0; i < size; i++)
        vector.push_back(rand_int(rng));
    return vector;
}

std::vector<int> smallVector(int size)
{
    std::vector<int> vector1{5, 4, 1, 2, 3};

    return vector1;
}

int main()
{
    std::vector<int> vector = randomizeIntVector(100000);
    std::vector<int> expectedVector = vector;
    quicksort(vector, 0, vector.size() - 1);
    std::sort(expectedVector.begin(), expectedVector.end());

    assert(vector == expectedVector);

}