Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 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)

Адаптивность: адаптивная сортировка умеет использовать уже существующий порядок входных данных, чтобы сократить вычисления и добиться лучшей эффективности. Лучшая временная сложность адаптивных алгоритмов обычно лучше их средней временной сложности.

Основанность на сравнении: сортировка на основе сравнений использует операторы сравнения (\(<\), \(=\), \(>\)), чтобы определить относительный порядок элементов и отсортировать массив. Нижняя граница ее временной сложности в худшем случае равна \(\Omega(n \log n)\) . А вот сортировка без сравнений не опирается на операторы сравнения, поэтому может достигать \(O(n)\) , но универсальность у нее ниже.

## 11.1.2 Идеальный алгоритм сортировки

Быстрый, выполняющийся на месте, стабильный, адаптивный и универсальный. Очевидно, что на сегодняшний день не существует алгоритма сортировки, который одновременно обладал бы всеми этими свойствами. Поэтому при выборе алгоритма сортировки нужно исходить из конкретных особенностей данных и требований задачи.

Далее мы последовательно изучим разные алгоритмы сортировки и на основании приведенных выше критериев разберем их преимущества и недостатки.

##### Оставляйте свои идеи, вопросы и предложения в комментариях