Алгоритмы сортировки через визуализации. Сортировка вставками
Этот курс целиком и полностью построен на анимациях и визуализациях, чтобы сделать алгоритмы наглядными и понятными для всех!
Это вторая глава курса про алгоритмы сортировки, которая посвящена сортировке вставками. В первой главе мы разбирали пузырьковую сортировку.
Курс подходит для новичков с базовыми навыками JavaScript. Если вы действующий разработчик, то пропускайте части с «разжёвыванием» кода.
Будем сортировать тот же массив из пяти элементов, с которым работали в первой главе:
[4, 1, 7, 2, 5]
Выведем его на экран с помощью специальной команды draw.
Детальный алгоритм сортировки вставками описан в комментариях в коде.
Алгоритм получил своё название «Сортировка вставками», потому что на каждом шаге часть массива слева становится полностью отсортированной, а новый элемент «вставляется» (insert) на нужное место в этой области.
Сейчас пошагово выполним этот алгоритм.
Сначала мы решим задачу «в лоб», без циклов, чтобы лучше прочувствовать алгоритм.
На первом этапе сортировки выберем ключ — второй элемент массива (с индексом 1) и сохраним его значение в переменную current для дальнейших сравнений. Отобразим ключ с помощью draw.
Не забудьте, нумерация элементов массива начинается с 0.
Сравним сохранённое значение 1 с предыдущим элементом 4. Предыдущий элемент больше, поэтому сдвигаем его вправо, чтобы освободить место для вставки текущего элемента.
С помощью draw отобразим текущее состояние массива.
Обратите внимание, как элементы массива при сдвиге вправо дублируются.
Мы дошли до начала списка. Значит, пора вставить ключ на нужное место.
Поместим значение 1 на первую позицию (индекс 0). Теперь отсортированная часть массива стала на один элемент больше и выглядит так: [1, 4].
Перейдём ко второму шагу сортировки.
Выберем новый ключ — третий элемент массива (элемент с индексом 2). Отобразим его.
Сравним ключ 7, с предыдущим элементом — 4. Предыдущий элемент меньше ключа, поэтому ключ остаётся на своём месте. А отсортированная часть массива увеличилась на один элемент и теперь выглядит так: [1, 4, 7].
Перейдём к третьему шагу сортировки.
Выберем в качестве ключа элемент с индексом 3 (значение 2).
Сравним ключ с предыдущим элементом (третьим по счёту). Сместим предыдущий элемент вправо, чтобы освободить место.
Сравним ключ со следующим элементом (вторым по счёту). Сместим и этот элемент вправо, чтобы освободить место для вставки.
Сравним ключ со следующим элементом (первым по счёту). Этот элемент меньше ключа. Значит, смещать элементы больше не нужно.
Вставим ключ в освободившуюся позицию — на место второго элемента массива.
Отсортированная часть массива увеличилась на один элемент и теперь выглядит так: [1, 2, 4, 7].
Перейдём к пятому шагу сортировки.
Выберем пятый элемент в качестве ключа.
Сравним ключ с предыдущим элементом (7). Сдвинем предыдущий элемент вправо, чтобы освободить место для вставки.
Сравним ключ со следующим элементом (4). Он меньше ключа, поэтому элементы не смещаем.
Вставим ключ на найденную позицию — четвёртое место в массиве.
Мы перебрали все элементы в массиве, работа алгоритма завершена.
Уберём все вспомогательные отрисовки состояний массива и посмотрим на анимацию работы нашего ручного алгоритма.
Теперь давайте спрячем ручную реализацию алгоритма «в лоб» в отдельную функцию.
Рядом с решением «в лоб» добавим «нормальную» функцию сортировки с циклами и условиями.
Создадим массив sameArr, такой же как arr. Отрисуем sameArr с помощью функции drawCompare, которая работает так же, как и draw, но выводит результат в соседний контейнер.
Создадим и вызовем пустую функцию insertionSort.
В конечном счёте insertionSort должна вести себя так же, как и ручной алгоритм. То есть состояния массива справа должны повторять состояния массива слева.
Начнём написание функции с цикла, внутри которого элементы «отсортированной» части массива сравниваются с ключом.
Сравнение пойдёт с конца «отсортированной части» к началу. В нашем случае удобно использовать цикл while, в котором переменная-счётчик уменьшается на каждой итерации.
Например, чтобы пройти от третьего элемента массива до первого, достаточно задать j = 2. В правой панели отрисуем пройденные элементы.
Поиск места для ключа завершится в двух случаях:
- Мы дошли до конца «отсортированной части».
- Мы встретили элемент, который меньше или равен ключу.
Для обработки второго случая добавим в цикл условие. Как только встретился элемент меньший или равный ключу, выходим из цикла с помощью break. В примере break сработал, когда мы дошли до единицы (второй элемент массива).
Настроим цикл для первого шага. Переменной j зададим значение 0, так как ключ нужно сравнить только с первым элементом массива. В условии сравним j со значением второго элемента массива, то есть с 1.
Чтобы сместить элемент, копируем код «как есть» из ручного алгоритма и вставляем внутри условия:
arr[1] = arr[0];
Чтобы вставить ключ на найденную позицию, копируем код «как есть» из ручного алгоритма. Вставим код после цикла:
arr[0] = 1;
Заменим статичные значения на переменные. Добавим переменную current и присвоим ей значение второго элемента массива. Затем используем эту переменную в условии и в операции вставки:
arr[j] > 1 → arr[j] > current
arr[0] = 1 → arr[0] = current
То же самое проделаем с индексом j. В операции смещения вправо заменим arr[1] = arr[0] на arr[j + 1] = arr[j].
В операции вставки ключа заменим arr[0] на arr[j + 1]. После выхода из цикла значение j будет равно -1, поэтому мы добавили единицу, чтобы получить нулевой индекс.
Теперь можно оценить код. Первый шаг в новой функции отработал так же, как и в старой. Значит, код работает правильно.
Для второго шага скопируем первый цикл и поменяем значения переменных перед запуском цикла.
На этом шаге ключ — третий элемент массива, значит, current = arr[2]. «Отсортированая часть» массива состоит из двух элементов, значит, j = 1.
Второй шаг отработал, так же, как и в ручном алгоритме. 7 осталась на своём месте.
Для третьего шага снова скопируем цикл и заменим значения переменных перед циклом.
На этом шаге ключ — четвёртый элемент массива, значит, current = arr[3]. «Отсортированая часть» массива состоит уже из трёх элементов, значит, j = 2.
И третий шаг отработал правильно. Пора переходить к созданию внешнего цикла, который отвечает за шаги алгоритма и изменение ключа.
Код внутри циклов while одинаковый. Отличается только код для настройки значений переменных перед циклами. Унифицируем его.
Введём переменную i. Заменим код настройки переменных на current = arr[i] и j = i - 1. Изменим значение i перед каждым циклом.
Состояния массива справа не изменились. Значит, рефакторинг прошёл успешно.
Создадим пустой цикл по переменной i, который отвечает за шаги алгоритма.
Обход списка должен начинаться со второго элемента, поэтому начальное значение i в цикле равно 1. Чтобы код работал с массивами любой длины, в качестве условия останова укажем i < arr.length.
Полностью скопируем код первого шага внутрь цикла, а сам код шагов закомментируем.
Проверим блок состояний — функция insertionSort работает точно так же, как и ручная реализация. Мы справились.
Почистим код — удалим комментарии внутри insertionSort.
Ещё немного изменим код. Добавим в условие останова внутри while проверку arr[j] > current. Так при встрече элемента, который меньше или равен ключу, цикл остановится сам.
После этих правок можно избавиться от условия и оператора break внутри цикла.
Удалим условие и break. Поведение сортировки не изменилось.
Хрестоматийная функция сортировки вставками готова! Дальше насладимся дополнительными анимациями и визуализациями сортировки.
Удалим функцию straightforwardSort и запустим анимацию работы алгоритма.
Проверим как работает алгоритм на другом массиве [2, 4, 6, 8, 1, 3, 7, 5].
Для сортировки вставками, как и для пузырьковой сортировки, самый неприятный случай — это массив, который отсортирован в обратном порядке.
Теперь, когда вы знакомы с двумя алгоритмами сортировки, можно сравнить их работу с помощью красивой анимированной тепловой карты!
На этой ноте глава про сортировку вставками завершена.
