Задача сортировки. Классификация и свойства сортировок

Задача сортировки. Что это такое и зачем нужно?

Сортировка - это алгоритмический процесс упорядочивания (перестановки) элементов множества по определенному критерию (ключу сортировки) по возрастанию или убыванию. Это одна из самых исследованных и фундаментальных задач информатики.

Сортировка редко является самоцелью. Чаще всего это важнейший этап предобработки данных. Как мы разбирали в предыдущем модуле, быстрый дихотомический (бинарный) поиск за логарифмическое время O(log N) возможен только в отсортированных массивах. Кроме того, сортировка нужна для группировки данных, быстрого устранения дубликатов и подготовки отчетов.

Классификация алгоритмов сортировки

За десятилетия развития информатики было придумано огромное количество алгоритмов сортировки. Чтобы в них ориентироваться, их классифицируют по пяти основным признакам:

1. По месту хранения данных: Внутренние и Внешние

• Внутренние сортировки: Весь массив данных полностью помещается в оперативную память (ОЗУ), что обеспечивает быстрый доступ. В этом модуле мы будем изучать именно их.
• Внешние сортировки: Данные настолько велики (например, база данных на терабайты), что не помещаются в ОЗУ. Они хранятся на жестком диске (медленный доступ) и сортируются поблочно (обычно вариациями сортировки слиянием).

2. По вычислительной сложности: Простые и Эффективные

• Простые сортировки O(N²): Сортировки вставкой, выборкой, пузырьковые. Они используют вложенные циклы и работают очень медленно на больших массивах, но идеальны для маленьких наборов данных (до 50-100 элементов, малых массивов) благодаря отсутствию накладных расходов.
• Эффективные сортировки O(N log N): Быстрая сортировка Хоара (Quick Sort), Пирамидальная сортировка (Heap Sort), сортировка слиянием (Merge Sort), Турнирная сортировка. Их основа - сложные структуры данных и рекурсия, что позволяет преодолеть ограничение квадратичной сложности и эффективно работать для больших объемов.

3. По типу базовой операции: Сравнениями и Распределяющие

• Сортировки сравнениями: Основаны на базовой операции сравнения двух ключей. Математически доказано, что нижняя граница времени для любого такого алгоритма составляет O(N log N). Быстрее отсортировать массив сравнениями невозможно.
• Распределяющие сортировки: Могут работать за линейное время O(N) (подсчетом, поразрядная, карманная). Они не сравнивают элементы между собой, а используют ключи как индексы или разряды для распределения по группам.

4. По использованию памяти: На месте и С дополнительной памятью

• Сортировки на месте: Требуют O(1) дополнительной памяти. Перестановка элементов происходит внутри самого массива (вставкой, выборкой, пирамидальная). Это крайне важное свойство при дефиците оперативной памяти (они экономят память).
• С дополнительной памятью: Требуют O(N) дополнительной памяти для работы (слияние, сортировка подсчетом, карманная). Создают временные массивы или списки, равные по размеру исходным данным (они создают копии).

5. По устойчивости

Устойчивая (стабильная) сортировка не меняет первоначальный относительный порядок элементов с одинаковыми ключами (сохранение первоначального относительного порядка одинаковых ключей гарантируется).

Представьте, что у вас есть список сотрудников, который уже отсортирован по фамилии по алфавиту. Теперь вы сортируете этот список по номеру отдела. Если алгоритм устойчивый, то внутри каждого отдела сотрудники останутся отсортированными по фамилии относительно друг друга (порядок сохраняется). Если алгоритм неустойчивый (применяются неустойчивые сортировки), алфавитный порядок внутри отделов нарушается и будет потерян (элементы меняются местами).

Базовый инструментарий (на C)

Любой алгоритм внутренней сортировки на Си строится вокруг двух простейших операций: Сравнение (if a[i] > a[j]) и Обмен (Swap). Функцию обмена мы будем использовать во всех алгоритмах курса:

#include <stdio.h>

// Универсальная функция обмена двух переменных (Swap)
void Swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Заглушка абстрактного алгоритма сортировки массива
void Sort(int arr[], int n) {
    // В следующих уроках мы будем заполнять эту функцию 
    // различными алгоритмами: от O(N^2) до O(N log N)
}