Алгоритмы сортировки через визуализации. Пузырёк
Алгоритмы — это не самая лёгкая тема, и многим она даётся с трудом. Алгоритмы слишком абстрактны, их сложно представлять, за ними сложно наблюдать.
Мы сделали курс, который целиком и полностью построен на анимациях и визуализациях, чтобы сделать алгоритмы наглядными и понятными для всех!
Это первая глава курса про алгоритмы сортировки. Она подходит для новичков с базовыми навыками JavaScript. Если вы действующий разработчик, то пропускайте части с «разжёвыванием» кода.
Сортировка — это популярная и одновременно интуитивно понятная задача, поэтому знакомство с алгоритмами часто начинают с неё. Перед нами массив из пяти элементов, который мы будем сортировать:
[4, 1, 7, 2, 5]
Выведем его на экран с помощью специальной команды draw.
После сортировки числа в массиве становятся по порядку — от меньшего к большему. Вы можете увидеть это на экране.
Алгоритмов сортировки множество. Но хрестоматийный — это «пузырёк». С него и начнём.
Кто пузырёк не писал — тот алгоритмов не видал.
Детальный алгоритм пузырьковой сортировки описан в комментариях в коде.
Он называется «пузырьковая сортировка», потому что наибольший или наименьший элемент «всплывает», как пузырёк, и оказывается на своём правильном месте.
Сейчас мы пошагово выполним этот алгоритм.
Сначала мы не будем писать никаких циклов и условий, а решим задачу «в лоб», чтобы лучше прочувствовать алгоритм.
У нас есть массив из пяти элементов [4, 1, 7, 2, 5]. При первом проходе по массиву мы должны сравнить первые два числа. Если первое число больше второго, то меняем их местами. Делаем это через дополнительную переменную.
4 больше 1, значит числа меняются местами.
Не забудьте, что нумерация элементов массива начинается с 0.
Давайте нарисуем массив, который получился после проверки первых двух чисел.
Снова используем функцию draw. Передадим в неё индексы переставленных элементов массива, чтобы подсветить их.
Сравним следующую пару — второе и третье число.
4 меньше 7, условие не сработает. Элементы остаются на своих местах.
Будем отрисовывать состояния массива после всех проверок, даже неудачных, чтобы наблюдать за всеми шагами алгоритма.
На этом шаге элементы местами не менялись, поэтому ничего не подсвечиваем.
Следующая пара — третье и четвёртое число. 7 больше 2, меняем числа местами.
Последняя пара первого прохода — четвёртое и пятое число. 7 больше 5, меняем числа местами.
Первый проход завершён. В конце массива находится самое больше число — 7. Можно переходить ко второму проходу.
При втором проходе нужно обработать первые четыре элемента. То есть на один элемент меньше, чем при первом проходе.
Второй проход начинаем с начала массива. Сравниваем первый и второй элементы. Ничего менять не нужно.
Следующая пара второго прохода — второй и третий элементы. Меняем их местами.
После перестановки массив уже будет отсортирован, но компьютер этого не «увидит». Он выполнит алгоритм от начала до конца.
Мы поступим так же. Пока есть элементы для сравнения, продолжим работать.
Третья и последняя пара второго прохода — третий и четвёртый элементы. Менять не надо. Проход завершён.
Начинаем третий проход. Он ещё на один элемент короче второго.
Сравниваем первое и второе число. Менять элементы не нужно.
Последняя пара третьего прохода — второй и третий элементы. Менять элементы не нужно. Проход завершён.
В четвёртом проходе сравнивается только одна пара элементов — первый и второй. Этот проход последний, так как в следующем нет элементов для сравнения. Работа алгоритма завершена.
Мы специально выполнили все шаги, чтобы показать, что в алгоритмах нет ничего волшебного и они могут оказаться неэффективными. «Пустые» проходы заняли у нас почти половину работы.
Конечная цель изучения алгоритмов — это умение подбирать эффективные алгоритмы для решения задач или оптимизировать существующие. Но об этом мы поговорим позже.
Сейчас наша задача — понять как работает «пузырёк», а не пытаться его оптимизировать. Поэтому примем его таким, какой он есть, — простым, но неэффективным.
Давайте покажем только те шаги, где элементы поменяются местами.
Видите, как большие числа «всплывают», пока сортировка не завершится?
Мы вручную выполнили алгоритм сортировки пузырьком. Теперь давайте спрячем его в отдельную функцию. Функцию так и назовём — «сортировка, решение в лоб».
Рядом с решением «в лоб» добавим «нормальную» функцию сортировки с циклами и условиями.
Создадим массив sameArr, который повторит содержимое массива arr. Отрисуем sameArr с помощью функции drawCompare, которая работает так же, как и draw, но выводит результат в другой контейнер.
Создадим новую функцию bubbleSort. Наша задача сделать так, чтобы функция вела себя в соответствии с алгоритмом. То есть состояния массива справа должны повторять состояния массива слева.
Состояния слева получены в результате внимательной, кропотливой, ручной реализации алгоритма, там всё работает правильно.
Начнём писать код по шагам. Сначала создадим пустой цикл для первого прохода.
В массиве 5 элементов, значит нам нужно последовательно сравнить 4 пары элементов. Поэтому зададим переменной i начальное значение 0 и условие останова i < 4. Это обеспечит выполнение 4 итераций сравнения.
Скопируем код перестановки значений из первого шага ручного алгоритма внутрь цикла.
Заменим статичные индексы в условии: вместо arr[0] запишем arr[i], а вместо arr[1] — arr[i + 1]. Эта запись обеспечит нужные значения на каждом шаге цикла.
Заменим статичные значения в операциях перестановки по аналогии с предыдущим шагом.
Момент истины! Добавляем функцию для отрисовки состояния массива.
Первый проход в новой функции отработал так же, как в старой. Значит, код работает правильно.
Для второго прохода скопируем первый цикл и заменим в нём условие останова на i < 3. Помним, что на каждом следующем проходе количество элементов уменьшается на один.
Состояния массивов совпадают. Всё работает правильно.
Мы копировали циклы для сравнения элементов внутри прохода. Давайте создадим цикл для самих проходов.
Циклы первого и второго прохода отличаются только значением условия останова i < 4 и i < 3. Сделаем код циклов одинаковым:
- добавим переменную
pass, - заменим условие останова на
4 - pass, - зададим нужное значение переменной
pass перед циклами.
Создадим цикл по переменной pass, который отвечает за проходы.
Полностью скопируем код любого из циклов для перестановки элементов внутрь нового цикла.
А код циклов первого и второго прохода пока закомментируем.
Проверим блок состояний — ничего не сломалось. Значит, всё работает правильно.
Удалим закомментированный код в функции bubbleSort.
Удалим функцию straightforwardSort. Она больше не нужна.
Доработаем функцию bubbleSort, чтобы она работала с массивами любого размера. Для этого создадим переменную n и запишем в неё длину массива arr для удобства уменьшенную на 1.
Заменим статичное значение 4 в условиях останова обоих циклов на переменную n.
Добавим в массив ещё одно число и проверим, что сортировка работает.
Хрестоматийная неоптимизированная функция пузырьковой сортировки готова! Дальше насладимся дополнительными анимациями и визуализациями сортировки.
Это анимация сортировки массива из прошлого шага.
Используем массив побольше и анимируем его сортировку.
А теперь самый неприятный для «пузырька» случай — массив, который отсортирован в обратном порядке.
Давайте посмотрим на «тепловую карту» работы алгоритма. В этой визуализации числам соответствуют цвета: меньше число — холоднее цвет, больше число — горячее.
На картах видно, как «горячие» значения постепенно «всплывают» вверх.
Ещё раз изменим массив.
А теперь снова массив, который отсортирован в обратном порядке.
Принцип работы «пузырька» лучше всего виден на этой карте. Смотрите, как последовательно и симметрично «всплывают» восьмёрка, семёрка и так далее.
На этой красивой ноте глава про пузырьковую сортировку завершена. Пришло время выполнить практическое задание, чтобы закрепить знания!
