Возникли проблемы с интроспективной сортировкой

Question

Я пытаюсь отсортировать массивы, используя разные алгоритмы. Кажется, что каждый алгоритм, который я использую, работает должным образом, однако мой IntroSort ведет себя странно. Он всегда медленнее, чем QuickSort, и для большого количества элементов, например миллиона, это занимает несколько минут, когда QuickSort занимает прибл. 1,2 секунды.

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

Функции, которые я использую (из файла gorithms.h )

#pragma once

template <typename T>
void display_array(T* arr, int n) {     // displays full array in one line
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

template <typename T>
void swap_values(T* x, T* y) {          // swaps two values
    T tmp = *x;
    *x = *y;
    *y = tmp;
}

/* * * * Quick Sort * * * */
template <typename T>
int quickS_part(T* arr, int left, int right) {
    int position = left;
    T pivot = arr[right];

    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap_values(&arr[i], &arr[position]);
            position++;
        }
    }

    swap_values(&arr[position], &arr[right]);

    return position;
}

template <typename T>
void quick_sort(T* arr, int left, int right) {
    if (left < right) {
        int pivot = quickS_part(arr, left, right);

        quick_sort(arr, left, pivot - 1);
        quick_sort(arr, pivot + 1, right);
    }
}

/* * * * Heap Sort * * * */
template <typename T>
void heapify(T* arr, int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < size && arr[left] > arr[largest])
        largest = left;
    if (right < size && arr[right] > arr[largest])
        largest = right;

    if (largest != root) {
        swap_values(&arr[root], &arr[largest]);
        heapify(arr, size, largest);
    }
}

template <typename T>
void heap_sort(T* arr, int size) {
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(arr, size, i);

    for (int i = size - 1; i >= 0; i--) {
        swap_values(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

/* * * * Insertion Sort * * * */
template <typename T>
void insertion_sort(T* arr, int left, int size) {
    for (int i = 1; i < size; i++) {
        T k = arr[i];
        int j = i - 1;
        while (k < arr[j] && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

/* * * * Introspective Sort * * * */
template <typename T>
void introS(T* arr, int left, int right, int maxdepth) {
    if ((right - left) < 16)
        insertion_sort(arr, left, right + 1);
    else if (maxdepth == 0)
        heap_sort(arr, right + 1);
    else {
        int pivot = quickS_part(arr, left, right);

        introS(arr, left, pivot - 1, maxdepth - 1);
        introS(arr, pivot + 1, right, maxdepth - 1);
    }
}

template <typename T>
void intro_sort(T* arr, int left, int right) {
    int md = 2 * floor(log(right + 1));
    introS(arr, left, right, md);
}

main. cpp:

#include <iostream>
#include <ctime>
#include <chrono>
#include <cmath>
#include "algorithms.h"

int main()
{
    //srand(time(NULL));

    const int size = 1000000;
    int *test1;
    test1 = new int[size];

    for (int i = 0; i < size; i++)
        test1[i] =  rand() % 1000000;

    auto start = std::chrono::high_resolution_clock::now();

    intro_sort(test1, 0, size - 1);

    auto end = std::chrono::high_resolution_clock::now();
    double time = std::chrono::duration<double, std::milli>(end - start).count();

    std::cout << "Sorting took " << time << " milliseconds." << std::endl;

    delete[] test1;
    return 0;
}

Answer 1

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

Это правильная версия, которая работала для меня:

Сортировка вставки:

template <typename T>
void insertion_sort(T* arr, int left, int size) {
    for (int i = left; i < size; i++) {
        T k = arr[i];
        int j = i - 1;
        while (k < arr[j] && j >= left) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

Сортировка кучи:

template <typename T>
void heap_sort(T* arr, int start, int size) {
    for (int i = size / 2 - 1; i >= start; i--)
        heapify(arr, size, i);                 // there are no changes in "heapify" function

    for (int i = size - 1; i >= start; i--) {
        swap_values(&arr[start], &arr[i]);
        heapify(arr, i, start);
    }
}

Интроспективная сортировка:

template <typename T>
void introS(T* arr, int left, int right, int maxdepth) {
    if ((right - left) < 16)
        insertion_sort(arr, left, right + 1);
    else if (maxdepth == 0)
        heap_sort(arr, left, right + 1);
    else {
        int pivot = quickS_part(arr, left, right);

        introS(arr, left, pivot - 1, maxdepth - 1);
        introS(arr, pivot + 1, right, maxdepth - 1);
    }
}