Основные характеристики сортировки.

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

Первая задача, которую получил Гоша с товарищами, — расположить населённые пункты в соответствии со значением этого индекса по возрастанию.

Гоша: Что может быть проще сортировки? Взять функцию из стандартной библиотеки и вперёд!

Тимофей: Между прочим, сортировки бывают разные. И не каждая из них одинаково подходит для определённого случая. Чтобы выбрать подходящий алгоритм, нужно проанализировать задачу и имеющиеся ресурсы. Оптимальный алгоритм для одной задачи может совершенно не подойти для решения другой.

Например, возьмём два алгоритма сортировки. Один работает быстро, но требует $O(n)$ дополнительной памяти. Другой алгоритм медленнее, но ему нужно $O(1)$дополнительной памяти.

Допустим, у вас есть интернет-магазин, и нужно считать статистику количества пользователей по дням. Данных много, и на сервере для статистики, где они хранятся, совсем нет свободной памяти. Результат работы алгоритма нужен не срочно.

А теперь представьте, что у вас мощный сервер с большим запасом памяти. На нём исполняется код, который влияет на скорость загрузки страницы. Конечно, клиент не захочет долго ждать у монитора, он рассчитывает увидеть результат на экране сразу после нажатия на кнопку или открытия страницы.

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

Если у вас всего 1000 товаров, то любой алгоритм сортировки упорядочит их так быстро, что пользователь не заметит. Если же у вас в наличии 5 000 000 товаров, разница может быть уже существенна.

То же самое касается и памяти. Если у вас в наличии объём свободной памяти, превосходящий объём данных, можно скопировать все данные в дополнительную память.

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

Использование дополнительной памяти — одна из ключевых характеристик сортировки.

Алла: Эх, что-то забыли мы спросить про это ограничение у Кондратия! Нужно уточнить.

Тимофей: Да, уточним. Ещё одна характеристика алгоритмов сортировки — устойчивость.

Если после работы алгоритма порядок равных элементов сохраняется, сортировка называется устойчивой. В противном случае — неустойчивой.

Предположим, нужно отсортировать города по количеству жителей.

В Котограде и Светлозаводск одинаковое количество жителей. Первый алгоритм сортировки сохранил их относительный порядок, а при использовании второго алгоритма порядок изменился.

В примере во втором алгоритме Свиреповск и Большие Утюги также поменялись местами. Но даже если бы порядок остался прежним, алгоритм все равно был бы неустойчивый. Одной инверсии в примере достаточно, чтобы сделать этот вывод.

Можно отметить важное свойство теории алгоритмов: при наличии одинаковых значений возможно несколько вариантов верно отсортированных последовательностей. Если сортировка устойчивая, последовательность ровно одна.

Рита: Про это тоже не спросили. Насколько я знаю, у Табулятинска, откуда родом любимый ручной скунс Кондратия, и села Пробелы один и тот же «треш-индекс» — четыре. В исходном списке Табулятинск идёт раньше. Вдруг Кондратий не хочет, чтобы после сортировки поменялся исходный порядок равных элементов?

Гоша: Да, нужно это выяснить.

Алла: Кстати, а сколько всего можно составить разных последовательностей из массива чисел?

Тимофей: Если все $n$ чисел в массиве различные, получится $n$ факториал разных последовательностей.

Алла: Почему факториал?

Допустим, дан массив чисел numbers:

Скопировать кодPYTHON
numbers = [2, 1, 5] 

Может быть всего 6 последовательностей.

Скопировать кодPYTHON
1 2 5
1 5 2
2 1 5
2 5 1
5 1 2
5 2 1 

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

По теореме умножения получаем: 3 х 2 х 1 = 6.

Это и есть формула вычисления факториала — произведение чисел от 0 до $n$.