Сортировка

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


Семейство алгоритмов сортировки

Семейство алгоритмов сортировки — сравнение временной сложности и характеристик

Простые сортировки (O(n²))

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

Продвинутые сортировки (O(n log n))

Быстрая сортировка, сортировка слиянием и пирамидальная сортировка наиболее широко используются в инженерии. Сортировка Шелла — это улучшение сортировки вставками.

Примеры

#include <stdio.h>

void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }

/* Пузырьковая сортировка — O(n²), устойчивая
На каждом проходе наибольший элемент «всплывает» в конец */

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  /* Оптимизация: досрочное завершение */
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }
        if (!swapped) break;  /* Уже отсортировано, завершить досрочно */
    }
}

/* Функция разбиения Quicksort — O(n log n) в среднем, неустойчивая
Выберите опорный элемент; элементы меньше опорного идут влево, больше — вправо */

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  /* Выбрать последний элемент в качестве опорного */
    int i = low - 1;        /* i указывает на конец области, элементы которой меньше pivot */
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);  /* Поместить pivot в правильную позицию */
    return i + 1;
}

void quickSort(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);  /* Рекурсивно отсортировать правую половину */
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = 7;
    bubbleSort(arr1, n1);
    printf("Сортировка пузырьком: "); printArray(arr1, n1);
    /* Вывод: 11 12 22 25 34 64 90 */

    int arr2[] = {64, 34, 25, 12, 22, 11, 90};
    quickSort(arr2, 0, 6);
    printf("Быстрая сортировка: "); printArray(arr2, 7);
    /* Вывод: 11 12 22 25 34 64 90 */
    return 0;
}

Иллюстрация концепции «разделяй и властвуй»

Три основных алгоритма сортировки O(n log n) — сравнение стратегий «разделяй и властвуй»

Быстрая сортировка (разбиение)

Выбор опорного элемента

Меньше опорного → левая сторона, больше → правая сторона

Рекурсивно отсортировать левый и правый подмассивы

Неустойчивая | На месте | Наиболее часто используется

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

Рекурсивно делить пополам до наименьшей единицы

Слить две упорядоченные подпоследовательности

Требует дополнительный массив O(n)

Устойчивая | Требует дополнительной памяти | Внешняя сортировка

Пирамидальная сортировка (Heapify)

Построение max-кучи O(n)

Переместить вершину кучи (максимум) в конец

Восстановить кучу O(log n)

Неустойчивая | На месте O(1) | Оптимальная по памяти

Полное сравнение алгоритмов сортировки

АлгоритмЛучшийСреднееХудшийПамятьСтабильность
Пузырьковая сортировкаO(n)O(n²)O(n²)O(1)Устойчивая
Сортировка выборомO(n²)O(n²)O(n²)O(1)Неустойчивая
Сортировка вставкамиO(n)O(n²)O(n²)O(1)Устойчивая
Быстрая сортировкаO(n log n)O(n log n)O(n²)O(log n)Неустойчивая
Сортировка слияниемO(n log n)O(n log n)O(n log n)O(n)Устойчивая
Пирамидальная сортировкаO(n log n)O(n log n)O(n log n)O(1)Неустойчивая
Сортировка ШеллаO(n log n)O(n^1.3)O(n²)O(1)Неустойчивая

Практический совет по выбору: для общих сценариев первый выбор — быстрая сортировка; выбирайте сортировку слиянием, когда нужна устойчивость; выбирайте пирамидальную сортировку при крайне ограниченной памяти; выбирайте сортировку вставками для небольших или почти отсортированных данных.

Другие расширения