Rivalry2

HTML Diff

1 added 1 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>11 мар 2022</li>

3 <li>0</li>

4 </ul><h2>Великая тройка: алгоритмы сортировки, которые точно пригодятся на собеседовании</h2>

5 Да кто такой этот ваш Bubble Sort?! Валерий Жила доступно рассказал о базовых алгоритмах сортировки и сравнил их характеристики.

6 Фото: Getty Images / Brandon Bell

7 Онлайн-журнал для тех, кто влюблён в код и информационные технологии. Пишем для айтишников и об айтишниках.

8 Software engineer, разрабатывает системы управления городской инфраструктурой для мегаполисов по всему миру. Основная деятельность: backend, database engineering. Ведёт твиттер<a>@ValeriiZhyla</a>.

9 Сегодня я расскажу простым языком о Bubble Sort, Insertion Sort и Selection Sort. Я покажу, какие идеи лежат в основе этих сортировок и продемонстрирую их сильные и слабые стороны. Мы разберём алгоритмы по шагам, рассмотрим их простые версии и даже немного улучшим.

10 Дальнейший рассказ подразумевает, что вас не смущают такие фразы, как "сложность worst-case-алгоритма по времени равна O(n^2)". Иногда Time Complexity я буду называть "сложностью по времени", а Space Complexity - "сложностью по памяти".

11 Если вы новичок в теории алгоритмов, сначала прочитайте<a>статью</a>Валерия о Big O Notation. В ней он человеческим языком рассказал, что такое алгоритмическая сложность и как её считать.

12 Давайте подумаем, на какие вопросы нужно ответить программисту, который собирается отсортировать элементы массива.

13 Сортировка оригинала.Недостаток этого решения в том, что мы потеряем изначальный массив. Представляет ли он ценность - зависит от ситуации. Тем не менее это лишний<a>побочный эффект (side effect)</a>работы алгоритма.

14 Зато нам не придётся выделять память под копию массива. Иначе Space Complexity выросла бы до O(n). А так имеемO(1)памяти. Красота! Кроме того, массив не придётся копировать, а значит, мы сэкономимO(n)у Time Complexity.

15 Сортировка копии (out-of-place).Здесь всё наоборот: никаких сторонних эффектов, зато сложность алгоритма по памяти и времени вырастает до O(n). Забегая вперёд, скажу, что лишнееO(n)времени на копирование не так уж и страшно по сравнению со временем на саму сортировку, которая сожрёт намного больше. А вот дополнительныеO(n)памяти - это серьёзный аргумент против out-of-place-алгоритмов.

16 Кадр: фильм "Звёздные войны: Эпизод 2 - Атака клонов"Напишем функцию, которая эффективно переставляет два элемента местами по их индексам:

17 def swap(int[] arr, fst_idx, snd_idx): int temp = arr[frst_idx] arr[frst_idx] = arr[snd_idx] arr[snd_idx] = tempФункцияswap()получает массив и два индекса. Сначала она сохраняет копию элемента с индексом frst_idx в переменнуюtemp. Затем записывает в элемент с индексом frst_idx содержимое элемента с индексомsnd_idx. В этот момент содержимое обоих элементов одинаковое, а оригинальное значениеfrst_idxхранится в temp. Поэтому мы записываем его в ячейкуsnd_idx.

18 Приведённые выше идентификаторы довольно часто используются в реальных программах. Временные значения хранят в переменнойtemp (сокращение от temporary, то есть "временный"). fst - это сокращение от first, snd - от second. А слово "индекс" часто обозначаютidx, потому что мы, программисты, не любим тратить буквы впустую :)

19 Было бы неплохо начать со сравнения элементов между собой. "Сравнивать-то можно, а что делать дальше?" - спросите вы. Как что? Менять их местами! Кажется, это действительно поможет навести порядок в нашем массиве… ну, или снизить уровень хаоса :)

20 Статья написана на основе<a>треда</a>Валерия в Twitter.

21 Будем сравнивать элементы с соседними индексами. Если значение левого элемента больше правого - поменяем их местами. Произвольный индекс массива назовёмi. Тогда у правого соседа будет индексi + 1. Теперь реализуем эту мысль в виде небольшого блока кода:

22 if arr[i] > arr[i + 1]: swap(arr, i, i + 1)Этот код - замечательная отправная точка для сортировки массива от меньшего элемента к большему. Но его нужно довести до ума.

23 Сперва применим описанные команды к каждому элементу массива. Разумеется, кроме последнего - иначе наша программа вышла бы за пределы массива и выдала ошибку. Отсюда и n - 1:

24 int n = arr.length for i in 0..n-1: if arr[i] > arr[i + 1]: swap(arr, i, i + 1)Этот код не отсортирует наш массив, но сделает его более упорядоченным. Вот небольшой пример его работы:

25 Скриншот: Skillbox MediaОбратите внимание: почти все элементы массива сместились в нужную сторону, а самый большой (9) оказался в крайней правой ячейке! На каждой итерации он менялся местами с соседом справа и "всплыл на поверхность".

26 Исполним наш код ещё несколько раз:

27 Скриншот: Skillbox MediaВсего за три прохода данные заметно упорядочились. Каждый виток гарантирует всплывание одного из элементов: на первом шаге число 9 встало на своё место, на втором - 8, а затем, по счастливой случайности, - сразу четыре элемента.

28 Сколько нужно сделать таких перестановок, чтобы гарантированно отсортировать массив? Если каждый проход выталкивает минимум один элемент, то через n проходов мы точно получим отсортированный массив! Даже черезn - 1, потому что у крайнего правого элемента останется только один вариант размещения.

29 int n = arr.length for j in 0..n-1: for i in 0..n-1: if arr[i] > arr[i + 1]: swap(arr, i, i + 1)Великолепно! Мы только что получили первый алгоритм сортировки. Итерация за итерацией - большие числа "всплывают", а меньшие "тонут". Очень давно кто-то увидел в этом аналогию с пузырьками воздуха в воде, поэтому такая сортировка называется пузырьковой, или Bubble Sort.

30 Наша версия "пузырька" вышла максимально наивной: и в лучшем, и в худшем случае его сложность по времени равнаO(n^2). Конечно, план надёжный как швейцарские часы, но его можно улучшить!

31 Мы знаем, что каждое выполнение внутреннего цикла гарантированно ставит на место один правый элемент. Значит, с каждым новым j можно сокращать диапазон прохода внутреннего цикла на единицу. Зачем трогать элементы, которые уже стоят на своих местах?

32 Поэтому в строке 3 добавляем смещение j:

33 int n = arr.length for j in 0..n-1: for i in 0..n-1-j: if arr[i] > arr[i + 1]: swap(arr, i, i + 1)Уже лучше, но программа всё ещё делает много лишней работы. Ведь за одну итерацию может "всплыть" сразу несколько элементов. Как добиться, чтобы программа останавливалась, когда массив будет полностью отсортирован? А вот как:

34 int n = arr.length int was_swapped = false for j in 0..n-1: was_swapped = false for i in 0..n-1-j: if arr[i] > arr[i + 1]: swap(arr, i, i + 1) was_swapped = true if was_swapped == false break;Мы ввели новую переменную, которая в начале внешнего цикла устанавливается в false и после каждого свопа меняет значение на true.

35 Если внутренний цикл не сделает ни одного свопа, переменная сохранит значение false и прервёт внешний цикл. Теперь сложность Best Case стала равна O(n)!

36 Если программа работает с изначально отсортированным массивом, то потребуется лишь один проход внутреннего цикла - чтобы обнаружить отсутствие перестановок и прервать внешний цикл. Вот это уже смахивает на Bubble Sort, который и на собесе не стыдно нарисовать!

37 Облачим код в функцию и продолжим полёт нашей фантазии:

38 def bubble_sort(int[] arr) int n = arr.length int was_swapped = false for j in 0..n-1: was_swapped = false for i in 0..n-1-j: if arr[i] > arr[i + 1]: swap(arr, i, i + 1) was_swapped = true if was_swapped == false break return arrВ таблице представлены значения Time Complexity для лучшего, среднего и худшего случаев входных данных, а также значение Space Complexity:

39 - NameBubbleNameBubbleWorstO(n^2)AverageO(n^2)BestO(n)SpaceO(1)В основе пузырьковой сортировки - сравнение соседних элементов массива. А как ещё можно отсортировать массив? Начнём с небольшой воображаем��й сцены.

39 + NameBubbleNameBubbleWorstO(n^2)AverageO(n^2)BestO(n)SpaceO(1)В основе пузырьковой сортировки - сравнение соседних элементов массива. А как ещё можно отсортировать массив? Начнём с небольшой воображаемой сцены.

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

41 Так, шаг за шагом, мальчик выстроит шеренгу из чисел. Несложно догадаться, что получившийся аналог массива будет отсортирован по возрастанию - слева лежит наименьшее число, справа - наибольшее. Примерно так работает наивная сортировка выбором, или Selection Sort. Давайте попробуем изобразить её в виде кода.

42 Нам понадобится функция для поиска индекса наименьшего элемента:

43 def find_min(int[] arr): int current_min_idx = 0 int current_min_value = arr[0] for i in 0..arr.length: if (arr[i] < current_min_value): current_min_value = arr[i] current_min_idx = i return current_min_idxМожно было бы обойтись безcurrent_min_value, но я оставлю эту переменную для наглядности.

44 Сутьfind_min()предельно проста. Будем считать, что первый элемент массива - это текущий минимум, и поочерёдно сравним его с другими элементами. Если какой-нибудь элемент меньше текущего минимума, то обновим значениеcurrent_min_value.

45 При этом мы обусловимся, что в массиве arr есть хотя бы один элемент и все ячейки заполнены числами. В противном случаеfind_min()станет ещё более страшным :)

46 Ещё нам нужна функция, которая удаляет элемент из массива. Максимально простая функция, исключительно красоты ради:

47 def delete_element(int[] arr, int idx): arr[idx] = nullИтак, приготовления завершены, и мы можем приступить к сортировке. Будем урезать оригинальный массив шаг за шагом, а результат выстраивать во втором массиве. Для этого сначала создадим пустой массив того же размера, что и оригинал.

48 А дальше реализуем шаги из нашего мысленного эксперимента в виде кода:

49 def native_selection_sort(int[] arr): int n = arr.length int[] sorted_arr = int[n] # пустой массив с n ячейками for i in 0..n: int idx_of_min_element = find_min(arr) sorted_arr[i] = arr[idx_of_min_element] delete_element(arr) return sorted_arrКакие замечания могут возникнуть к этому алгоритму:

50 <ul><li>Он ест слишком много памяти.Мы создаём отдельный массив под результат и получаемO(n)по памяти.</li>

51 <li>В оригинальном массиве появляются дыры.Функцияdelete_element()создаёт пустые ячейки в arr, о которые споткнётсяfind_min().</li>

52 <li>Высокая Time Complexity.Алгоритм явно не блещет скоростью исполнения -O(n^2)как в худшем, так и в лучшем случае.</li>

53 </ul>Возникает резонный вопрос: что же делать? Сейчас может быть немного непонятно, но обещаю, что дальше всё встанет на свои места.

54 Вот код оптимальной Selection Sort. Он упорядочивает элементы сразу в arr,а не создаёт дополнительный массив:

55 def selection_sort(int[] arr): int n = arr.length for i in 0..n: min_idx = find_min_between(arr, i + 1, n) swap(arr, i, min_idx) return arrКомпактно, правда? Я добавил функциюfind_min_between(array, start_idx, end_idx). Она работает как уже знакомаяfind_min(array),только проходит не по всему массиву, а по отрезку междуstart_idxи end_idx. Функцияswap(array, i, j)тоже в представлении не нуждается.

56 Теперь разберёмся, как работает улучшенная версия Selection Sort. Возьмём массивarrс десятью числами:

57 Скриншот: Skillbox MediaПройдёмся по массиву несколько раз циклом из selection_sort()и посмотрим на состояниеarr. Вот что мы получим:

58 Скриншот: Skillbox MediaЧтобы сохранять упорядоченные элементы в левой части массиваarr, алгоритм использует барьер между отсортированной и неотсортированной частью. Этот барьер находится между элементами с индексамиiи (i + 1).

59 В каждой итерации алгоритм ищет наименьшее значение в правой части (от i + 1 и до конца массива) и меняет его местами с элементом по индексу i. Приi = 1в отсортированной части массива будет только один элемент. При i = 2 - два.

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

61 Скриншот: Skillbox MediaОбратите внимание: состояниеarrпоказывается в конце каждой итерации. Первая строчка при i = 0, вторая при i = 1 и так далее.

62 Надеюсь, теперь идея Selection Sort кажется простой и естественной. Давайте взглянем на характеристики алгоритма.

63 С одной стороны, у такой реализации хорошая сложность по памятиO(1)за счёт использования левой части массива. С другой - поиск минимального элемента съедаетO(n)времени и повторяется в каждом цикле (nраз). Поэтому мы получаем и Worst Case, и Best Case равныеO(n^2), а это нехорошо.

64 Выходит, Bubble Sort быстрее, чем Selection Sort из-за Best CaseO(n)? Тут как в известном анекдоте: есть один нюанс. В конце статьи мы ещё обсудим аспекты, которые не учитывает О-нотация.

65 Дополним нашу таблицу с характеристиками:

66 NameBubbleSelectionNameBubbleSelectionWorstO(n^2)O(n^2)AverageO(n^2)O(n^2)BestO(n)O(n^2)SpaceO(1)O(1)Insertion Sort, она же сортировка вставками, очень похожа на Selection Sort. Я даже называю её "Selection Sort наоборот", потому что она действует по обратному принципу.

67 Напомню, что в Selection Sort мы искали наименьший элемент в правой части, переставляли его в конец левой и шли дальше. Самая дорогая операция в этом алгоритме - поиск наименьшего элемента.

68 В Insertion Sort мы тоже сохраняем упорядоченные элементы в исходном массиве. Только на этот раз из правой части берём первый попавшийся элемент и выбираем, куда его вставить в левой.

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

70 Работа Insertion Sort немного напоминает толкучку в общественном транспорте. Боксёр-тяжеловес, который зайдёт в набитый трамвай, вероятно, спровоцирует движение всех пассажиров на полшага от выхода.

71 Рассмотрим пример такой вставки. У нас есть отсортированный массив из восьми чисел со свободной ячейкой в конце. Нужно добавить в этот массив число 5 на правильную позицию. Вот как будет выглядеть алгоритм:

72 int[] arr = [1, 2, 3, 4, 6, 7, 8, 9, _] int key = 5 int element_to_move_idx = arr.length - 2 # arr[arr.length - 2] = 9 while (element_to_move_idx >= 0) and (key < arr[element_to_move_idx]): arr[element_to_move_idx + 1] = arr[element_to_move_idx] element_to_move_idx-- #вставляем новое значение в пустую ячейку arr[element_to_move_idx + 1] = keyНачнём передвигать числа больше 5 вправо:

73 Скриншот: Skillbox MediaОбратите внимание: справа от передвигаемого числа возникает его копия, а оригинал перезаписывается соседом слева на следующей итерации.

74 А вот как выглядит массив после всех сдвиганий:

75 Скриншот: Skillbox MediaКогда цикл дойдёт до 4, он остановится и запишет число 5 вместо "мусорной" шестёрки.

76 Скриншот: Skillbox MediaТеперь взглянем на заветный код Insertion Sort:

77 def insertion_sort(int[] arr): int n = arr.length for i in 1..n: key = arr[i] # передвигаем в отсортированную часть элементы, которые больше, чем key int element_to_move_idx = i - 1 while (element_to_move_idx >= 0) and (key < arr[element_to_move_idx]): arr[element_to_move_idx + 1] = arr[element_to_move_idx] element_to_move_idx-- #вставляем новое значение в пустую ячейку arr[element_to_move_idx + 1] = key return arrПомните барьер из Selection Sort? Так как алгоритм похож, предлагаю повторить такой же трюк с Insertion Sort:

78 Скриншот: Skillbox MediaНижняя граница производительности довольно привлекательна. Если массив изначально отсортирован, то ничего сдвигать не нужно! Сложность Best Case у такой сортировки составляетO(n).

79 Мы разобрали "Великую Тройку Сортировок", с которой неизбежно сталкивается любой, кто изучает алгоритмы. С чем я всех и поздравляю!

80 Стабильным (устойчивым, stable) называется алгоритм сортировки, который не меняет порядок элементов с одинаковыми ключами относительно друг друга. Если мы сортируем числа, то стабильность особой роли не играет, а вот если сортируем объекты, то очень даже.

81 Допустим, нужно отсортировать по возрасту массив с записями о клиентах. Для наглядности возьмём максимально простой вид записей в формате [возраст : имя].

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

83 Скриншот: Skillbox MediaВ нестабильном варианте допускается второй сценарий:

84 Скриншот: Skillbox MediaСтабильность крайне важна, если мы планируем сортировать массив объектов по нескольким ключам. Например, сначала по возрасту, потом по размеру банковского счёта и затем по площади жилья. В таком случае нестабильный алгоритм испортит нам всю малину.

85 В нашей тройке стабильными являются Bubble Sort и Insertion Sort, а вот Selection Sort так и норовит перемешать элементы.

86 Дополним нашу таблицу характеристиками Selection Sort и строкой с показателями стабильности:

87 NameBubbleSelectionInsertionNameBubbleSelectionInsertionWorstO(n^2)O(n^2)O(n^2)AverageO(n^2)O(n^2)O(n^2)BestO(n)O(n^2)O(n)SpaceO(1)O(1)O(1)StableyesnoyesЯ обещал обсудить нюансы, которые не учитывает O-нотация. Пришло время перемывать косточки уже полюбившимся алгоритмам!

88 Посмотрим на почти идеально отсортированный массив. Почти - потому что самый большой элемент в нём стоит на первом месте:

89 Скриншот: Skillbox MediaКак поведут себя алгоритмы:

90 <ul><li>Bubble Sortсработает великолепно. За nперестановок наибольший элемент "всплывёт" наверх.</li>

91 <li>Insertion Sortтоже хорош в этом вопросе.</li>

92 <li>Selection Sortсо страшной расточительностью перелопатит весь массив и выдастO(n^2)по времени.</li>

93 </ul>Вывод:если данные почти отсортированы, то Bubble Sort и Insertion Sort - наши лучшие друзья.

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

95 Например, прочитать значение в ячейке массива - элементарно. Перезаписать ячейку - вроде бы тоже просто, да вот только многопоточность, обновление значений в кэше процессора и другие факторы реального мира с этим не согласны. Поэтому операцияswap()не так уж и проста, как кажется на первый взгляд.

96 А вот что у нас по количеству свопов:

97 <ul><li>Bubble Sortпросто монстр, который свопает без остановки. Количество операций записи здесь зашкаливает.</li>

98 <li>Insertion Sortтоже не подарок - постоянное сдвигание элементов вправо до добра не доведёт.</li>

99 <li>Selection Sort - конфетка! Всегоnсвопов в худшем случае. Очень экономичный алгоритм.</li>

100 </ul>Вывод:если стоит задача сэкономить на операциях записи, то Selection Sort - лучший выбор.

101 Что касается памяти, то все три алгоритма в этом одинаково хороши. Они работают in-place и поэтому съедаютO(1)памяти.

102 Отмечу, что алгоритмы сортировки можно улучшать. В основном с помощью особых структур данных. Например, Insertion Sort можно ускорить примерно в два раза, а также свести количество свопов к показателям Bubble Sort, если использовать не массив, а связный список. А Selection Sort можно сделать стабильным.

103 Код сортировок на разных языках программирования и видео с визуализацией можно найти на сайте<a>geeksforgeeks.org</a>:

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

105 <li><a>Selection Sort</a></li>

106 <li><a>Insertion Sort</a></li>

107 </ul>На YouTube полно визуализаций алгоритмов сортировки, но я выделю это видео:

108 Отдельный мем в этой теме - венгерские танцы. Выглядит не только познавательно, но и очень забавно:)

109 Кажется, на этом тема простых сортировок исчерпана. Надеюсь, удалось всё разложить по полочкам и никого не запутать. В следующих статьях об алгоритмах разберу Merge Sort и Quick Sort и постараюсь залезть в материал поглубже.

110 <a>Научитесь: Алгоритмы и структуры данных для разработчиков Узнать больше</a>