Почему быстрая сортировка на месте медленнее, чем обычная версия в C ++?

Question

В XCode моей macOS я сделал тест таймера для quicksort. Когда количество моего элемента равно 10, 100. Пока я не установил количество, подобное 1000, время работы моей версии на месте становится медленнее, чемдругая версия.Я использую C ++, чтобы сделать этот тест.вот код моей основной функции:

    const int sort_size = 100000;
    clock_t begin, end;
    vector<int> vec_1;
    srand((unsigned)time(NULL));
    for (auto i = 0; i < sort_size; ++i) {
        auto r = rand() % sort_size;
        vec_1.push_back(r);
    }
    vector<int> vec_2(vec_1);
    begin = clock();
    auto sort_1 = QuickSort::exec(vec_1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);
    begin = clock();
    auto sort_2 = QuickSort::exec_in_place(vec_2, 0, sort_size - 1);
    end = clock();
    printf("%lfs\n", (double)(end - begin) / CLOCKS_PER_SEC);

Обе две функции использовали статическое объявление.

вот код версии на месте:

vector<int> QuickSort::exec_in_place(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }
    auto pivot = [=, &nums] () {
        auto pivot_idx = begin + (end - begin) / 2;
        auto pivot_val = nums[pivot_idx], idx_1 = begin;
        std::swap(nums[pivot_idx], nums[end]);
        for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
            if (nums[idx_2] > pivot_val) continue;
            std::swap(nums[idx_1], nums[idx_2]);
            idx_1++;
        }
        std::swap(nums[idx_1], nums[end]);
        return idx_1;
    }();
    exec_in_place(nums, begin, pivot - 1);
    exec_in_place(nums, pivot + 1, end);
    return nums;
}

Я попытался вытащить лямбда-функцию и упаковать ее в другую статическую функцию, но результат все тот же.

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

vector<int> QuickSort::exec(const vector<int> &nums) {
    if (nums.size() < 2) {
        return nums;
    }
    auto pivot = nums[0];
    vector<int> smaller;
    vector<int> greater;
    for (auto i = 1; i < nums.size(); ++i) {
        int num = nums.at(i);
        if (num < pivot) {
            smaller.push_back(num);
        } else {
            greater.push_back(num);
        }
    }
    auto smaller_nums = exec(smaller);
    auto greater_nums = exec(greater);
    smaller_nums.push_back(pivot);
    smaller_nums.insert(smaller_nums.end(), greater_nums.begin(), 
    greater_nums.end());
    return smaller_nums;
}

С тех пор, как я установил количество, такое как 1000, 10000 и т. Д. На месте начал замедляться.Например, когда сумма равна 1000, на месте тратят 0,005356сек, но в обычной версии используется 0,001464сек.когда количество достигает примерно 100 Кб, версия на месте составляет около 50 с, но нормальная версия - около 0,5 с.Может кто-нибудь сказать мне, почему 101

Извините за любые грамматические ошибки, английский не мой родной язык.

Answer 1

Не могу комментировать, но в версии на месте вам не нужна лямбда, и вам не нужно возвращать вектор. Не проверено, с минимальными изменениями исходного кода:

void exec_in_placex(vector<int> &nums, int begin, int end) {
    if (begin >= end) {
        return;
    }

    auto pivot_idx = begin + (end - begin) / 2;
    auto pivot_val = nums[pivot_idx], idx_1 = begin;
    std::swap(nums[pivot_idx], nums[end]);
    for (auto idx_2 = begin; idx_2 <= end - 1; ++idx_2) {
        if (nums[idx_2] > pivot_val) continue;
        std::swap(nums[idx_1], nums[idx_2]);
        idx_1++;
    }
    std::swap(nums[idx_1], nums[end]);
    auto pivot = idx_1;

    exec_in_placex(nums, begin, pivot - 1);
    exec_in_placex(nums, pivot + 1, end);
}