Разбираемся с сортировкой данных OTUS
2026-03-10 02:09 Diff
https://otus.ru/journal/razbiraemsya-s-sortirovkoj-dannyh/1-1-3/

При изучении алгоритмов и структур данных нередко поднимается тема сортировки элементов данных. Если говорить честно, необходимость в реализации какой-нибудь уникальной сортировки при работе со связанными структурами данных возникает довольно редко, а то и не возникает вовсе. Дело в том, что в современных языках программирования для этих целей существуют свои оптимизированные методы (тот же array.sort() в JavaScript). Так зачем же изучать данный вопрос? Дело в том, что это хороший пример как алгоритмов, так и баланса между расходом памяти и времени. В этой статье мы рассмотрим 2 самых популярных метода сортировки с разным расходованием ресурсов: Bubble Sort и Merge Sort. Для примера будем использовать язык программирования JavaScript.

Bubble Sort

Идея заключается в том, чтобы, выполняя проход массиву, находить элемент с наибольшим значением, одновременно с этим «протаскивая» его в конец. Если учесть, что за одну операцию обхода мы «дотаскиваем» лишь 1 максимальный элемент, чтобы реализовать Bubble Sort, нам надо будет выполнить n-операций по обходу (здесь n — это длина массива). Таким образом, мы получаем квадратичную алгоритмическую сложность O(n^2).

Но до того как погрузиться в реализацию, давайте сначала рассмотрим визуализацию описанного выше процесса:

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

Теперь реализуем это в коде:

Может, применение Bubble Sort с ее аж квадратичной алгоритмической сложностью не так уж и практично, ведь есть и более универсальные решения, связанные с сортировкой данных? На деле все не так просто, ведь вышеописанный метод имеет одно существенное преимущество — расход памяти. Для смены мест 2-х элементов нам понадобится только одна вспомогательная переменная, в результате чего мы получаем константную сложность по памяти. А это огромный плюс, если сравнивать с сортировкой слиянием, которую мы сейчас рассмотрим.

Merge Sort

Вот, как она выглядит:

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

  1. Разбить структуру данных пополам на 2 новых массива.
  2. Разбить каждую половину снова пополам, потом опять пополам и так до тех пор, пока не останутся массивы, содержащие лишь 1 элемент.
  3. Выполнить операцию обратного слияния (попарно), но уже сортируя компоненты по возрастанию.

Из-за постоянной разбивки и попарного слияния алгоритмическая сложность используемой процедуры составляет O(n * log n).

Смотрим на основной код:

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

В чем же логика? Смотрите, к нам «приходят» два массива: правый и левый. Оба или уже отсортированы, или просто включают в себя лишь 1 компонент. Далее надо начинать обходить обоих (потребуется лишь один обход с 2-мя указателями: первый укажет на итерируемый компонент левого массива, второй — на компонент правого), причем брать — наименьший из 2-ух элементов, забрасывая его в новую структуру, которую мы и возвратим как отсортированную.

Вот наш код:

Теперь должно быть все понятно.

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

Вывод прост: более быстрая сортировка потребует существенно больше памяти. Также можно сказать еще кое-что: Bubble Sort и Merge Sort — это, по сути, одни из лучших универсальных методов сортировки. А все потому, что они стабильно работают практически в любых случаях и с любыми данными (в пределах разумного). Да, есть методы, выигрывающие по алгоритмической сложности, к примеру, Radix Sort. Но практическое использование подобных методов специфично, поэтому их вряд ли можно назвать универсальными.

Несколько советов

Парочка полезных рекомендаций:

  • совсем не обязательно наизусть знать все структуры данных и алгоритмы;
  • самые нужные в плане пользы знания, чаще всего являются наиболее простыми в плане освоения;
  • не надо помнить все реализации — все мы люди, поэтому какие-то реализации можно и забыть. Но на практике вам будет достаточно 1 раз в них разобраться и иметь представление об их возможностях;
  • анализируйте свои алгоритмы. Надо задумываться над их эффективностью — это полезно;
  • чем более эффективный код вам удается создавать, тем более высокую производительность и надежность будет демонстрировать ваш программный продукт (как следствие — тем более крутым разработчиком вы будете).

По материалам: https://dou.ua/lenta/articles/what-you-should-know-about-algorithms/.

Какие еще статьи можно дополнительно почитать на тему структур данных:

— «Структуры и типы данных»;

— «Понятие структуры данных для программиста. Массивы»;

— «Топ-8 структур данных для программиста»;

— «Дерево как структура данных. Двоичные деревья».

Изучив эти статьи, вы будете знать, что такое структуры данных, зачем они используются, как происходит распределение данных в зависимости от структуры, какие операции поддерживаются, что такое графы, деревья, боры и связные списки, какое значение имеет словосочетание first out, как обратиться к элементу в списке и т. д.