Сортировка
Сортировка — это процесс упорядочивания множества объектов (элементов) по определённому признаку, как правило, в возрастающем или убывающем порядке. В информатике и математике сортировка является одной из фундаментальных операций обработки данных, позволяющей ускорить последующий поиск, анализ и представление информации. Сортировка может применяться к числам, строкам, записям баз данных и любым другим объектам, для которых задано отношение порядка.
Основные понятия и классификация
Сортировка характеризуется рядом ключевых параметров: алгоритмом, временной сложностью, используемой памятью и устойчивостью. Под устойчивостью (стабильностью) понимается сохранение относительного порядка равных элементов после сортировки. Сортировка может быть внутренней (вся обрабатываемая информация помещается в оперативную память) и внешней (данные хранятся на внешних носителях, и требуется обмен с ними).
Классификация по принципу работы
Алгоритмы сортировки делятся на несколько основных классов:
- Сортировка сравнением — алгоритмы, которые определяют порядок элементов путём их попарного сравнения. К этому классу относится большинство классических методов (пузырьковая, быстрая, сортировка слиянием).
- Сортировка распределением — алгоритмы, которые не сравнивают элементы напрямую, а распределяют их по ключам или корзинам (поразрядная сортировка, карманная сортировка).
- Сортировка подсчётом — используется для целых чисел из ограниченного диапазона. Подсчитывается количество вхождений каждого значения, после чего строится отсортированный массив.
История развития
Первые упоминания о формальных алгоритмах сортировки относятся к началу XX века. В 1918 году американский инженер Герман Холлерит использовал сортировку перфокарт для обработки данных переписи населения США. В 1945 году Джон фон Нейман предложил сортировку слиянием, которая стала первым алгоритмом с гарантированной сложностью O(n log n). В 1956 году был опубликован метод быстрой сортировки (Тони Хоар), который до сих пор широко применяется. В 1960-х годах появились поразрядная сортировка и сортировка Шелла. В последующие десятилетия разрабатывались адаптивные и гибридные алгоритмы, сочетающие преимущества разных методов.
Основные алгоритмы сортировки
Простые (квадратичные) алгоритмы
Эти алгоритмы имеют временную сложность O(n²) и эффективны только для небольших массивов (до нескольких сотен элементов).
- Пузырьковая сортировка (Bubble Sort) — многократный проход по массиву, при котором каждый элемент сравнивается со следующим и, если порядок нарушен, меняется местами. Название получила из-за того, что большие элементы «всплывают» в конец массива.
- Сортировка вставками (Insertion Sort) — на каждом шаге один элемент из неотсортированной части вставляется в правильное место в отсортированной части. Эффективна для почти упорядоченных массивов.
- Сортировка выбором (Selection Sort) — на каждом проходе находится минимальный элемент и ставится в начало неотсортированной части.
Эффективные (логарифмические) алгоритмы
Эти алгоритмы имеют временную сложность O(n log n) и являются стандартом для больших массивов.
- Быстрая сортировка (Quicksort) — рекурсивный алгоритм, основанный на разделении массива на две части относительно опорного элемента (pivot). Все элементы меньше опорного помещаются слева, больше — справа. Затем процесс повторяется для каждой части. В среднем работает очень быстро, но в худшем случае (например, на уже отсортированном массиве) может деградировать до O(n²).
- Сортировка слиянием (Merge Sort) — рекурсивный алгоритм, разбивающий массив на две половины, сортирующий каждую половину отдельно, а затем сливающий их в один упорядоченный массив. Гарантирует O(n log n) в любом случае, но требует дополнительной памяти O(n).
- Пирамидальная сортировка (Heapsort) — использует структуру данных «куча» (heap). Сначала из массива строится максимальная куча, затем корень (максимальный элемент) меняется с последним элементом, размер кучи уменьшается, и процесс повторяется. Работает за O(n log n) без дополнительной памяти.
Специализированные алгоритмы
- Поразрядная сортировка (Radix Sort) — сортирует числа по разрядам (единицы, десятки, сотни и т.д.) с помощью устойчивой сортировки (например, сортировки подсчётом). Временная сложность — O(n * k), где k — количество разрядов. Эффективна для чисел фиксированной длины.
- Карманная сортировка (Bucket Sort) — распределяет элементы по корзинам (buckets), каждая из которых сортируется отдельно (обычно вставками или рекурсивно). Требует равномерного распределения данных.
- Сортировка подсчётом (Counting Sort) — для целых чисел в диапазоне [0, m] создаётся массив счётчиков размера m+1. Затем подсчитывается количество каждого числа, и массив заполняется в порядке возрастания. Сложность O(n + m).
Сравнение алгоритмов
| Алгоритм | Средняя сложность | Худшая сложность | Дополнительная память | Устойчивость |
|---|---|---|---|---|
| Пузырьковая | O(n²) | O(n²) | O(1) | Да |
| Вставками | O(n²) | O(n²) | O(1) | Да |
| Выбором | O(n²) | O(n²) | O(1) | Нет |
| Быстрая | O(n log n) | O(n²) | O(log n) | Нет |
| Слиянием | O(n log n) | O(n log n) | O(n) | Да |
| Пирамидальная | O(n log n) | O(n log n) | O(1) | Нет |
| Поразрядная | O(n * k) | O(n * k) | O(n + k) | Да (при устойчивой под-сортировке) |
| Подсчётом | O(n + m) | O(n + m) | O(m) | Да |
Применение сортировки
Сортировка является неотъемлемой частью множества прикладных задач:
- Базы данных — упорядочивание записей по заданному полю (имя, дата, цена) для быстрого поиска и отчётности.
- Поисковые системы — сортировка результатов поиска по релевантности, дате или популярности.
- Статистика и анализ данных — построение гистограмм, нахождение медианы, квартилей и других порядковых статистик.
- Компьютерная графика — сортировка полигонов по глубине (Z-буферизация) для корректного отображения сцены.
- Сжатие данных — некоторые алгоритмы сжатия (например, BWT) используют сортировку для повышения эффективности кодирования.
- Операционные системы — сортировка файлов в каталогах, списков процессов, задач планировщика.
Интересные факты
- В стандартной библиотеке языка C++ функция
std::sortобычно реализует гибридный алгоритм — быструю сортировку с переключением на пирамидальную или сортировку вставками для малых подмассивов (Introsort). - В языке Java для сортировки примитивных типов используется Dual-Pivot Quicksort (двухопорная быстрая сортировка), а для объектов — Timsort (гибрид сортировки слиянием и вставками).
- Существуют алгоритмы сортировки, работающие за O(n) в особых условиях (например, на графах или при наличии дополнительной информации о данных).
- В 2000-х годах была разработана сортировка сетями (sorting networks) — параллельные алгоритмы, где операции сравнения и обмена выполняются одновременно.
Источники
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (3-е издание). — М.: Вильямс, 2013.
- Кнут Д. «Искусство программирования. Том 3. Сортировка и поиск» (2-е издание). — М.: Вильямс, 2000.
- Седжвик Р. «Фундаментальные алгоритмы на C++. Анализ. Структуры данных. Сортировка. Поиск». — М.: ДиаСофт, 2001.
- Статья «Sorting algorithm» в англоязычной Википедии (версия от 15.10.2023).
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →