Lesta games Test task №3

gistfile1.txt

Для сортировки массива чисел на языке C/C++ с минимальными затратами процессорных тиков можно использовать алгоритм QuickSort. 
QuickSort часто является самым быстрым алгоритмом для сортировки случайных данных из-за его средней временной сложности 
O(nlog⁡n) и хороших характеристик кэш-памяти. 
Важно также оптимизировать QuickSort для улучшения производительности в реальных условиях.

В моем варианте данный алгоритм оптимизирован при помощи median of three для выбора опорного 
элемента и переключением на вставочную сортировку для маленьких массивов:
#include <iostream>
#include <algorithm>

// Порог для использования вставочной сортировки
const int INSERTION_SORT_THRESHOLD = 10;

// Вставочная сортировка
void insertionSort(int* arr, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

// Функция для обмена двух элементов
inline void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Функция для нахождения медианы трёх
int medianOfThree(int* arr, int a, int b, int c) {
    if (arr[a] < arr[b]) {
        if (arr[b] < arr[c]) return b;
        else if (arr[a] < arr[c]) return c;
        else return a;
    } else {
        if (arr[a] < arr[c]) return a;
        else if (arr[b] < arr[c]) return c;
        else return b;
    }
}

// Основная функция быстрой сортировки
void quickSort(int* arr, int left, int right) {
    if (left + INSERTION_SORT_THRESHOLD <= right) {
        int mid = medianOfThree(arr, left, (left + right) / 2, right);
        swap(arr[left], arr[mid]);

        int pivot = arr[left];
        int i = left + 1;
        int j = right;

        while (true) {
            while (i <= right && arr[i] <= pivot) ++i;
            while (j >= left && arr[j] > pivot) --j;

            if (i < j) {
                swap(arr[i], arr[j]);
            } else {
                break;
            }
        }
        swap(arr[left], arr[j]);

        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);
    } else {
        insertionSort(arr, left, right);
    }
}

// Функция-обёртка для удобства
void quickSort(int* arr, int size) {
    if (size > 1) {
        quickSort(arr, 0, size - 1);
    }
}

// Пример использования
int main() {
    int arr[] = {3, 6, 8, 10, 1, 2, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, size);

    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

Пояснения:
1. Median-of-three: 
Выбор медианы трёх для опорного элемента уменьшает вероятность выбора худшего опорного элемента, 
что повышает общую производительность.

2. Вставочная сортировка для маленьких массивов: 
Вставочная сортировка эффективна для небольших массивов и обеспечивает лучшую производительность, 
чем QuickSort для малых подмассивов.

3. Хорошая производительность в среднем случае: 
QuickSort с median-of-three и вставочной сортировкой имеет временную сложность O(nlog⁡n) в среднем, 
что делает его очень быстрым на практике для большинства входных данных.