Какие знаешь алгоритмы сортировки?

Основные алгоритмы сортировки в C++

Вот обзор наиболее известных алгоритмов сортировки с их характеристиками и применением.

1. Пузырьковая сортировка (Bubble Sort)

Сравнивает соседние элементы и меняет их местами.

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

• Сложность: O(n²) в среднем и худшем случаях, O(n) в лучшем
• Память: O(1)
• Стабильность: Стабильна
• Применение: Обучение, очень маленькие массивы

2. Сортировка выбором (Selection Sort)

Находит минимальный элемент и ставит его на место.

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        std::swap(arr[i], arr[minIdx]);
    }
}

• Сложность: O(n²) всегда
• Память: O(1)
• Стабильность: Не стабильна
• Применение: Когда нужно минимизировать обмены

3. Сортировка вставками (Insertion Sort)

Вставляет элемент на правильное место в отсортированную часть.

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

• Сложность: O(n) в лучшем (уже отсортирован), O(n²) в среднем/худшем
• Память: O(1)
• Стабильность: Стабильна
• Применение: Почти отсортированные массивы, маленькие массивы

4. Сортировка слиянием (Merge Sort)

Делит массив пополам, рекурсивно сортирует, затем объединяет.

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (int i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

• Сложность: O(n log n) всегда
• Память: O(n) дополнительной памяти
• Стабильность: Стабильна
• Применение: Когда нужна гарантированная O(n log n), внешняя сортировка

5. Быстрая сортировка (Quick Sort)

Выбирает опорный элемент, разбивает массив, рекурсивно сортирует части.

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            std::swap(arr[++i], arr[j]);
        }
    }
    std::swap(arr[++i], arr[high]);
    return i;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

• Сложность: O(n log n) в среднем, O(n²) в худшем случае
• Память: O(log n) для стека рекурсии
• Стабильность: Не стабильна
• Применение: Общая сортировка, встроена в std::sort

6. Сортировка кучей (Heap Sort)

Использует бинарную кучу для сортировки.

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // Построить кучу
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // Извлечь элементы из кучи
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

• Сложность: O(n log n) всегда
• Память: O(1)
• Стабильность: Не стабильна
• Применение: Когда нужна O(n log n) с O(1) памятью

7. Сортировка подсчётом (Counting Sort)

Предполагает, что элементы — целые числа в известном диапазоне.

void countingSort(std::vector<int>& arr) {
    int maxVal = *std::max_element(arr.begin(), arr.end());
    int minVal = *std::min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    
    std::vector<int> count(range, 0);
    std::vector<int> output(arr.size());
    
    // Подсчитаем элементы
    for (int x : arr)
        count[x - minVal]++;
    
    // Накопительная сумма
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];
    
    // Построим отсортированный массив
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }
    
    arr = output;
}

• Сложность: O(n + k), где k — диапазон значений
• Память: O(n + k)
• Стабильность: Стабильна (если правильно реализовать)
• Применение: Целые числа в ограниченном диапазоне

8. Поразрядная сортировка (Radix Sort)

Сортирует числа по разрядам (цифрам).

void radixSort(std::vector<int>& arr) {
    if (arr.empty()) return;
    
    int maxNum = *std::max_element(arr.begin(), arr.end());
    
    for (int exp = 1; maxNum / exp > 0; exp *= 10) {
        std::vector<int> bucket(10);
        std::vector<int> output(arr.size());
        
        // Подсчитаем элементы по текущему разряду
        for (int x : arr)
            bucket[(x / exp) % 10]++;
        
        // Накопительная сумма
        for (int i = 1; i < 10; i++)
            bucket[i] += bucket[i - 1];
        
        // Построим отсортированный массив
        for (int i = arr.size() - 1; i >= 0; i--) {
            output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
            bucket[(arr[i] / exp) % 10]--;
        }
        
        arr = output;
    }
}

• Сложность: O(d * n), где d — количество разрядов
• Память: O(n + k)
• Стабильность: Стабильна
• Применение: Сортировка целых чисел и строк

Сравнительная таблица

Встроенная сортировка в C++

#include <algorithm>
#include <vector>

std::vector<int> arr = {5, 2, 8, 1, 9};

// std::sort - обычно использует quicksort/introsort (гибрид)
std::sort(arr.begin(), arr.end());  // O(n log n) в среднем

// std::stable_sort - стабильная сортировка (merge sort)
std::stable_sort(arr.begin(), arr.end());

// std::partial_sort - частичная сортировка
std::partial_sort(arr.begin(), arr.begin() + 3, arr.end());

// std::nth_element - n-й наименьший элемент
std::nth_element(arr.begin(), arr.begin() + 2, arr.end());

Выбор алгоритма

• Для общего случая: std::sort (автоматический выбор лучшего)
• Когда нужна стабильность: std::stable_sort или merge sort
• Маленькие массивы: insertion sort (используется в std::sort)
• Целые числа: counting sort или radix sort
• Уже отсортирован: insertion sort с early exit
• Для обучения: bubble/selection/insertion sort

Ключевые моменты

• Quicksort и Mergesort — самые популярные O(n log n) алгоритмы
• std::sort в STL использует introsort (гибрид quicksort + heapsort)
• Стабильность важна только если нужно сохранить порядок равных элементов
• Выбирайте алгоритм на основе размера данных и требований к памяти