11.1 Алгоритмы сортировки¶
Алгоритмы сортировки (sorting algorithm) используются для упорядочивания набора данных по определенному правилу. Они применяются очень широко, потому что упорядоченные данные обычно проще и быстрее искать, анализировать и обрабатывать.
Как показано на рисунке 11-1, данными в алгоритмах сортировки могут быть целые числа, числа с плавающей запятой, символы, строки и другие типы. Критерий сравнения тоже можно задать по-разному, например по величине чисел, по порядку ASCII-кодов символов или по пользовательскому правилу.
Рисунок 11-1 Примеры типов данных и правил сравнения
11.1.1 Критерии оценки¶
Скорость выполнения: мы ожидаем, что временная сложность алгоритма сортировки будет как можно ниже, а общее число операций будет как можно меньше (то есть константа во временной сложности будет небольшой). Для больших объемов данных этот критерий особенно важен.
Сортировка на месте: как следует из названия, сортировка на месте выполняется прямо в исходном массиве и не требует дополнительного вспомогательного массива, что позволяет экономить память. Обычно при сортировке на месте переносов данных меньше, а скорость работы выше.
Стабильность: стабильная сортировка после завершения не меняет относительный порядок одинаковых элементов в массиве.
Стабильность является необходимым условием для многоуровневой сортировки. Предположим, у нас есть таблица со сведениями о студентах, где в первом и втором столбцах записаны имя и возраст. В этом случае нестабильная сортировка может разрушить уже существующий порядок входных данных:
# Входные данные уже отсортированы по имени
# (name, age)
('A', 19)
('B', 18)
('C', 21)
('D', 19)
('E', 23)
# Если затем нестабильным алгоритмом отсортировать список по возрасту,
# относительный порядок ('D', 19) и ('A', 19) изменится,
# и свойство упорядоченности по имени будет потеряно
('B', 18)
('D', 19)
('A', 19)
('C', 21)
('E', 23)
Адаптивность: адаптивная сортировка умеет использовать уже существующий порядок входных данных, чтобы сократить вычисления и добиться лучшей эффективности. Лучшая временная сложность адаптивных алгоритмов обычно лучше их средней временной сложности.
Основанность на сравнении: сортировка на основе сравнений использует операторы сравнения (\(<\), \(=\), \(>\)), чтобы определить относительный порядок элементов и отсортировать массив; ее теоретически лучшая временная сложность равна \(O(n \log n)\) . А вот сортировка без сравнений не опирается на операторы сравнения, поэтому может достигать \(O(n)\) , но универсальность у нее ниже.
11.1.2 Идеальный алгоритм сортировки¶
Быстрый, выполняющийся на месте, стабильный, адаптивный и универсальный. Очевидно, что на сегодняшний день не существует алгоритма сортировки, который одновременно обладал бы всеми этими свойствами. Поэтому при выборе алгоритма сортировки нужно исходить из конкретных особенностей данных и требований задачи.
Далее мы последовательно изучим разные алгоритмы сортировки и на основании приведенных выше критериев разберем их преимущества и недостатки.