Сортировка пузырьком
Шаг 1.
Алгоритмы — это не самая лёгкая тема, и многим она даётся с трудом. Алгоритмы слишком абстрактны, их сложно представлять, за ними сложно наблюдать.
Мы сделали курс, который целиком и полностью построен на анимациях и визуализациях, чтобы сделать алгоритмы наглядными и понятными для всех!
Это первая глава курса про алгоритмы сортировки. Она подходит для новичков с базовыми навыками JavaScript. Если вы действующий разработчик, то пропускайте части с «разжёвыванием» кода.
Шаг 2.
Сортировка — это популярная и одновременно интуитивно понятная задача, поэтому знакомство с алгоритмами часто начинают с неё. Перед нами массив из пяти элементов, который мы будем сортировать:
[4, 1, 7, 2, 5]
Выведем его на экран с помощью специальной команды draw.
Шаг 3.
После сортировки числа в массиве становятся по порядку — от меньшего к большему. Вы можете увидеть это на экране.
Алгоритмов сортировки множество. Но хрестоматийный — это «пузырёк». С него и начнём.
Кто пузырёк не писал — тот алгоритмов не видал.
Шаг 4.
Детальный алгоритм пузырьковой сортировки описан в комментариях в коде.
Он называется «пузырьковая сортировка», потому что наибольший или наименьший элемент «всплывает», как пузырёк, и оказывается на своём правильном месте.
Сейчас мы пошагово выполним этот алгоритм.
Шаг 5.
Сначала мы не будем писать никаких циклов и условий, а решим задачу «в лоб», чтобы лучше прочувствовать алгоритм.
У нас есть массив из пяти элементов [4, 1, 7, 2, 5]. При первом проходе по массиву мы должны сравнить первые два числа. Если первое число больше второго, то меняем их местами. Делаем это через дополнительную переменную.
4 больше 1, значит числа меняются местами.
Не забудьте, что нумерация элементов массива начинается с 0.
Шаг 6.
Давайте нарисуем массив, который получился после проверки первых двух чисел.
Снова используем функцию draw. Передадим в неё индексы переставленных элементов массива, чтобы подсветить их.
Шаг 7.
Сравним следующую пару — второе и третье число.
4 меньше 7, условие не сработает. Элементы остаются на своих местах.
Шаг 8.
Будем отрисовывать состояния массива после всех проверок, даже неудачных, чтобы наблюдать за всеми шагами алгоритма.
На этом шаге элементы местами не менялись, поэтому ничего не подсвечиваем.
Шаг 9.
Следующая пара — третье и четвёртое число. 7 больше 2, меняем числа местами.
Шаг 10.
Последняя пара первого прохода — четвёртое и пятое число. 7 больше 5, меняем числа местами.
Первый проход завершён. В конце массива находится самое больше число — 7. Можно переходить ко второму проходу.
При втором проходе нужно обработать первые четыре элемента. То есть на один элемент меньше, чем при первом проходе.
Шаг 11.
Второй проход начинаем с начала массива. Сравниваем первый и второй элементы. Ничего менять не нужно.
Шаг 12.
Следующая пара второго прохода — второй и третий элементы. Меняем их местами.
После перестановки массив уже будет отсортирован, но компьютер этого не «увидит». Он выполнит алгоритм от начала до конца.
Мы поступим так же. Пока есть элементы для сравнения, продолжим работать.
Шаг 13.
Третья и последняя пара второго прохода — третий и четвёртый элементы. Менять не надо. Проход завершён.
Шаг 14.
Начинаем третий проход. Он ещё на один элемент короче второго.
Сравниваем первое и второе число. Менять элементы не нужно.
Шаг 15.
Последняя пара третьего прохода — второй и третий элементы. Менять элементы не нужно. Проход завершён.
Шаг 16.
В четвёртом проходе сравнивается только одна пара элементов — первый и второй. Этот проход последний, так как в следующем нет элементов для сравнения. Работа алгоритма завершена.
Мы специально выполнили все шаги, чтобы показать, что в алгоритмах нет ничего волшебного и они могут оказаться неэффективными. «Пустые» проходы заняли у нас почти половину работы.
Конечная цель изучения алгоритмов — это умение подбирать эффективные алгоритмы для решения задач или оптимизировать существующие. Но об этом мы поговорим позже.
Шаг 17.
Сейчас наша задача — понять как работает «пузырёк», а не пытаться его оптимизировать. Поэтому примем его таким, какой он есть, — простым, но неэффективным.
Давайте покажем только те шаги, где элементы поменяются местами.
Видите, как большие числа «всплывают», пока сортировка не завершится?
Шаг 18.
Мы вручную выполнили алгоритм сортировки пузырьком. Теперь давайте спрячем его в отдельную функцию. Функцию так и назовём — «сортировка, решение в лоб».
Шаг 19.
Рядом с решением «в лоб» добавим «нормальную» функцию сортировки с циклами и условиями.
Создадим массив sameArr, который повторит содержимое массива arr. Отрисуем sameArr с помощью функции drawCompare, которая работает так же, как и draw, но выводит результат в другой контейнер.
Шаг 20.
Создадим новую функцию bubbleSort. Наша задача сделать так, чтобы функция вела себя в соответствии с алгоритмом. То есть состояния массива справа должны повторять состояния массива слева.
Состояния слева получены в результате внимательной, кропотливой, ручной реализации алгоритма, там всё работает правильно.
Шаг 21.
Начнём писать код по шагам. Сначала создадим пустой цикл для первого прохода.
В массиве 5 элементов, значит нам нужно последовательно сравнить 4 пары элементов. Поэтому зададим переменной i начальное значение 0 и условие останова i < 4. Это обеспечит выполнение 4 итераций сравнения.
Шаг 22.
Скопируем код перестановки значений из первого шага ручного алгоритма внутрь цикла.
Шаг 23.
Заменим статичные индексы в условии: вместо arr[0] запишем arr[i], а вместо arr[1] — arr[i + 1]. Эта запись обеспечит нужные значения на каждом шаге цикла.
Шаг 24.
Заменим статичные значения в операциях перестановки по аналогии с предыдущим шагом.
Шаг 25.
Момент истины! Добавляем функцию для отрисовки состояния массива.
Первый проход в новой функции отработал так же, как в старой. Значит, код работает правильно.
Шаг 26.
Для второго прохода скопируем первый цикл и заменим в нём условие останова на i < 3. Помним, что на каждом следующем проходе количество элементов уменьшается на один.
Состояния массивов совпадают. Всё работает правильно.
Шаг 27.
Мы копировали циклы для сравнения элементов внутри прохода. Давайте создадим цикл для самих проходов.
Циклы первого и второго прохода отличаются только значением условия останова i < 4 и i < 3. Сделаем код циклов одинаковым:
- добавим переменную
pass, - заменим условие останова на
4 - pass, - зададим нужное значение переменной
pass перед циклами.
Шаг 28.
Создадим цикл по переменной pass, который отвечает за проходы.
Шаг 29.
Полностью скопируем код любого из циклов для перестановки элементов внутрь нового цикла.
А код циклов первого и второго прохода пока закомментируем.
Проверим блок состояний — ничего не сломалось. Значит, всё работает правильно.
Шаг 30.
Удалим закомментированный код в функции bubbleSort.
Шаг 31.
Удалим функцию straightforwardSort. Она больше не нужна.
Шаг 32.
Доработаем функцию bubbleSort, чтобы она работала с массивами любого размера. Для этого создадим переменную n и запишем в неё длину массива arr для удобства уменьшенную на 1.
Заменим статичное значение 4 в условиях останова обоих циклов на переменную n.
Шаг 33.
Добавим в массив ещё одно число и проверим, что сортировка работает.
Хрестоматийная неоптимизированная функция пузырьковой сортировки готова! Дальше насладимся дополнительными анимациями и визуализациями сортировки.
Шаг 34.
Это анимация сортировки массива из прошлого шага.
Шаг 35.
Используем массив побольше и анимируем его сортировку.
Шаг 36.
А теперь самый неприятный для «пузырька» случай — массив, который отсортирован в обратном порядке.
Шаг 37.
Давайте посмотрим на «тепловую карту» работы алгоритма. В этой визуализации числам соответствуют цвета: меньше число — холоднее цвет, больше число — горячее.
На картах видно, как «горячие» значения постепенно «всплывают» вверх.
Шаг 38.
Ещё раз изменим массив.
Шаг 39.
А теперь снова массив, который отсортирован в обратном порядке.
Принцип работы «пузырька» лучше всего виден на этой карте. Смотрите, как последовательно и симметрично «всплывают» восьмёрка, семёрка и так далее.
На этой красивой ноте глава про пузырьковую сортировку завершена. Пришло время выполнить практическое задание, чтобы закрепить знания!
