Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 <ul><li><a>Bubble Sort</a></li>

2 <li><a>Merge Sort</a></li>

3 <li><a>Несколько советов</a></li>

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

5 <h2>Bubble Sort</h2>

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

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

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

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

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

11 <h2>Merge Sort</h2>

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

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

14 <ol><li>Разбить структуру данных пополам на 2 новых массива.</li>

15 <li>Разбить каждую половину снова пополам, потом опять пополам и так до тех пор, пока не останутся массивы, содержащие лишь 1 элемент.</li>

16 <li>Выполнить операцию обратного слияния (попарно), но уже сортируя компоненты по возрастанию.</li>

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

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

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

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

21 Вот наш код:

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

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

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

25 <h2>Несколько советов</h2>

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

27 <ul><li>совсем не обязательно наизусть знать все структуры данных и алгоритмы;</li>

28 <li>самые нужные в плане пользы знания, чаще всего являются наиболее простыми в плане освоения;</li>

29 <li>не надо помнить все реализации - все мы люди, поэтому какие-то реализации можно и забыть. Но на практике вам будет достаточно 1 раз в них разобраться и иметь представление об их возможностях;</li>

30 <li>анализируйте свои алгоритмы. Надо задумываться над их эффективностью - это полезно;</li>

31 <li>чем более эффективный код вам удается создавать, тем более высокую производительность и надежность будет демонстрировать ваш программный продукт (как следствие - тем более крутым разработчиком вы будете).</li>

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

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

34 - "<a>Структуры и типы данных</a>";

35 - "<a>Понятие структуры данных для программиста. Массивы</a>";

36 - "<a>Топ-8 структур данных для программиста</a>";

37 - "<a>Дерево как структура данных. Двоичные деревья</a>".

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

39 <a></a>