Все мы что-то сортировали в реальной жизни. Многие упорядочивали книги на полке по названию, автору или даже размеру. Кто-то до сих пор хранит бумажные счета за коммунальные услуги и держит их упорядоченными по дате. Но все люди сортируют по-разному: кто-то сваливает все книги в кучу и начинает выставлять их уже в отсортированном порядке, кто-то просто начинает переставлять книги на полке, а кто-то держит свою полку в идеальном состоянии и при новых покупках просто ставит книгу сразу в нужное место. Сортировок очень и очень много, в этой главе мы посмотрим на самые частые из них и разберём их свойства и сложности.

Свойства сортировок

Сортировки классифицируются по многим своим характеристикам, для ознакомления приведём самые частые из них.

Использование памяти и асимптотическая сложность

Мы можем оценить алгоритмы сортировок по времени их выполнения и по объёму занимаемой в процессе памяти.

Устойчивость

Сортировка считается устойчивой (stable), если при равенстве элементов в процессе сортировки она не меняет их местами.

Пример работы устойчивой сортировки

Тогда как неустойчивая сортировка не принимает во внимание нахождение элементов в изначальном массиве.

Пример работы неустойчивой сортировки

Так, например, если бы мы сортировали книги «на месте», не скидывая изначально в кучу, то, скорее всего, мы бы сортировали устойчиво: зачем нам менять местами две книги Ахматовой, если они равны в алфавитном порядке? А если бы мы сначала свалили их в кучу, то могли бы выставить в любом порядке — всё равно по итогу они будут стоять рядом.

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

Использование операций сравнения

Некоторые сортировки, например radix sort, не нуждаются в использовании сравнения элементов внутри массива, но работают только с ограниченными наборами данных.

Естественность

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

В следующих пунктах этой главы посмотрим на самые популярные алгоритмы сортировок и реализуем их.