Как эффективно отсортировать 1 миллион целых чисел?

Как эффективно отсортировать 1 миллион целых чисел

Сортировка 1 миллиона целых чисел требует учёта алгоритма, кэша процессора и параллелизма. Нет универсального решения, всё зависит от характеристик данных.

1. std::sort (Лучший выбор в большинстве случаев)

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

int main() {
    std::vector<int> data(1000000);
    
    // Заполнить случайными числами
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(0, 999999);
    for (int& x : data) x = dis(gen);
    
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(data.begin(), data.end());
    auto end = std::chrono::high_resolution_clock::now();
    
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(
        end - start).count();
    std::cout << "std::sort: " << ms << " ms" << std::endl;
    
    return 0;
}

Характеристики std::sort:

• Алгоритм: Introsort (QuickSort + HeapSort)
• Временная сложность: O(n log n)
• Пространственная: O(log n)
• Стабильность: НЕ стабильна
• Производительность: отличная на случайных данных

2. std::stable_sort для сохранения порядка

std::stable_sort(data.begin(), data.end());

Характеристики:

• Временная сложность: O(n log n)
• Пространственная: O(n)
• Стабильность: ДА
• Скорость: немного медленнее std::sort

3. Radix Sort для целых чисел

void radixSort(std::vector<int>& arr) {
    int maxValue = *std::max_element(arr.begin(), arr.end());
    
    for (int exp = 1; maxValue / exp > 0; exp *= 10) {
        std::vector<int> output(arr.size());
        std::vector<int> count(10, 0);
        
        for (int x : arr) {
            count[(x / exp) % 10]++;
        }
        
        for (int i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }
        
        for (int i = arr.size() - 1; i >= 0; --i) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        
        arr = output;
    }
}

Характеристики:

• Временная сложность: O(d * n) где d ≈ log₁₀(max)
• Пространственная: O(n + k)
• Преимущество: часто быстрее std::sort на целых числах

4. Counting Sort для ограниченного диапазона

void countingSort(std::vector<int>& arr, int maxValue) {
    std::vector<int> count(maxValue + 1, 0);
    
    for (int x : arr) {
        count[x]++;
    }
    
    int index = 0;
    for (int i = 0; i <= maxValue; ++i) {
        for (int j = 0; j < count[i]; ++j) {
            arr[index++] = i;
        }
    }
}

Используй когда:

• Целые числа в известном диапазоне
• Диапазон не слишком большой (сравним с n)
• Временная сложность: O(n + k)
• Пространственная: O(k)

5. Параллельная сортировка (C++17)

#include <execution>

std::sort(std::execution::par, data.begin(), data.end());

// Или unsequenced (может быть ещё быстрее)
std::sort(std::execution::par_unseq, data.begin(), data.end());

Требования:

• C++17 или позже
• Компилятор поддерживает Execution Policies
• Пример: g++ -std=c++17 -ltbb

Оптимизации производительности

Используй смежную память

std::vector<int> good;  // Смежная память - хорошо для кэша
std::list<int> bad;     // Несмежная память - плохо

// std::sort работает только с RandomAccessIterator
// поэтому список нужно сначала скопировать в вектор

Избегай сложных компараторов

// Плохо
std::sort(data.begin(), data.end(), 
    [](const int& a, const int& b) {
        if (a % 2 != b % 2) return a % 2 < b % 2;
        return a < b;
    });

// Хорошо - преобразовать данные предварительно
std::vector<std::pair<int, int>> pairs;
for (int x : data) pairs.push_back({x % 2, x});
std::sort(pairs.begin(), pairs.end());

Сравнение алгоритмов на 1 млн чисел

Финальная рекомендация

int main() {
    std::vector<int> data(1000000);
    // ... заполнить данные ...
    
    // Для большинства случаев:
    std::sort(data.begin(), data.end());
    
    // Если есть C++17 и нужна многопоточность:
    std::sort(std::execution::par, data.begin(), data.end());
    
    // Если целые числа в малом диапазоне:
    // используй counting sort или radix sort
    
    return 0;
}

Вывод: std::sort — правильный выбор для 99% случаев. Используй параллельную версию если доступны многоядерные системы. Radix/Counting sort только если данные имеют специальные свойства.