На прошлой неделе я написал блог о сортировке выбором. Давайте продолжим наше путешествие по алгоритму сортировки и обсудим сортировку вставками. Концептуально я нахожу сортировку вставками похожей на сортировку выбором. Однако вместо того, чтобы находить минимум в несортированном разделе массива, мы будем искать в уже отсортированных элементах в начале массива, чтобы узнать, куда поместить каждый последующий элемент. Например, наши первые два элемента — это 3 и 1, мы поменяем их местами, чтобы они располагались в порядке возрастания (1, за которым следует 3). После этого, если бы у нас была 2, мы бы поместили ее между 1 и 3. По этой причине сортировка вставками сравнивается с тем, как вы сортируете игральные карты в руке.

Пошаговый пример

Ожидаемый результат

Сортировать по возрастанию
Ввод: [4, 2, 5, 1, 3, 6]
Вывод: [1, 2, 3, 4, 5, 6]

Первая итерация

На самом деле мы начнем с элемента с индексом 1. Нам нужно будет сохранить этот элемент в переменной, чтобы отслеживать его. Назовем эту переменную current.
Итак, current = 2. Оттуда мы проверим, меньше ли элемент перед current чем current. В данном случае 2 ‹ 4, поэтому мы просмотрим элементы до current, чтобы выяснить, где нам нужно его присвоить.

Первый шаг — это перемещение числа, превышающего current, в индекс перед ним, временно у нас будет повторяющееся число в нашем массиве, и мы не увидим current в массиве. Вот почему мы сохраняем его значение в переменной для хранения.
[4, 2, 5, 1, 3, 6] → [ 4, 4, 5, 1, 3, 6]

Мы достигли начала нашего массива, поэтому мы знаем, что current — это наименьшее число в отсортированном разделе массива на данный момент, и мы назначим current индексу 0.
[4 , 4, 5, 1, 3, 6] → [2, 4, 5, 1, 3, 6]

Вторая итерация

Итак, мы начали с индекса 1, теперь current нужно присвоить следующему элементу с индексом 2.
Итак, current = 5. Число, предшествующее current, равно 4.

4 ‹ 5, поэтому нам ничего делать не нужно.
[2, 4, 5, 1, 3, 6] → [2, 4, 5, 1, 3, 6]

Третья итерация

current = 1, а так как 1 ‹ 5, нам нужно будет придумать, куда поставить 1.

переместить 5 вверх на один индекс
[2, 4, 5, 1, 3, 6] → [2, 4, 5 , 5, 3, 6]

current ‹ 4, поэтому переместите 4 на один индекс вверх
[2, 4, 5, 5, 3, 6] → [2, 4, 4, 5, 3, 6]

current ‹ 2, переместите 2 вверх
[2, 4, 4, 5, 3, 6] → [2, 2 , 4, 5, 3, 6]

Мы достигли начала массива, мы знаем, что current — наименьшее число на данный момент, мы присвоим ему индекс 0.
[2, 2, 4, 5, 3, 6 ] → [1, 2, 4, 5, 3, 6]

Четвертая итерация

current = 3
 3 < 5
[1, 2, 4, 5, 3, 6] → [1, 2, 4, 5, 5, 6]

current < 4
[1, 2, 4, 5, 5, 6] → [1, 2, 4, 4, 5, 6]

current › 2, поэтому мы поместим его в отсортированный раздел нашего массива
[1, 2, 4, 4, 5, 6] → [1, 2, 3, 4, 5, 6]

Финальная итерация

current = 6 и 6 › 5, ничего делать не нужно
[1, 2, 3, 4, 5, 6] → [1, 2 , 3, 4, 5, 6]

Теперь наш массив отсортирован, и мы прошлись по каждому элементу массива, так что мы закончили. Даже если бы наш массив начинался отсортированным, ему все равно нужно было бы пройтись по каждому элементу массива, чтобы проверить, что current больше, чем элемент в индексе перед ним.

Код

function insertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let current = arr[i];
        let j = i - 1;
        while(j >= 0 && arr[j] > current){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
    return arr;
}

Объяснение кода

Мы начинаем наш цикл for с i = 1, это то же самое, что и в нашем пошаговом примере. Причина в том, что мы можем начать с элемента с индексом 1. Оттуда мы назначаем нашу переменную current, а затем переменную j = i - 1, поэтому мы можем начать наш цикл while, сравнивая current с элементом перед ним.

Условие цикла while (j >= 0 && arr[j] > current) заключается в том, что мы будем продолжать итерацию в обратном направлении по отсортированному разделу массива, пока элемент не станет меньше текущего или пока мы не окажемся в начале массива.

На каждой итерации нашего цикла while мы присваиваем элементу после j значение j. Это похоже на наше поведение при перемещении элемента. Вот почему мы временно видим дубликаты в нашем массиве. Оттуда мы уменьшаем j, так как хотим двигаться назад по отсортированному разделу массива к индексу 0. Мы выйдем из цикла while, как только элемент с индексом j станет не меньше current или мы достигнем начала множество.

Как только мы вышли из цикла while, у нас все еще есть значение current, которое отсутствует в массиве. current больше не меньше значения в j, поэтому нам нужно присвоить его элементу послеj. Это имитирует поведение нашего пошагового примера, здесь мы назначаем current первому повторяющемуся значению в массиве.

Сложность времени и пространства

Сложность времени

Подобно сортировке выбором, временная сложность сортировки вставками составляет n*(n-1)/2. Это связано с тем, что в худшем случае массив находится в обратном порядке, и внешний цикл должен будет выполняться один раз для каждого элемента. Тогда внутренний цикл сначала должен будет запуститься для замены первых двух элементов, а затем запуститься еще раз для каждого последующего элемента, потому что отсортированный раздел массива будет увеличиваться на 1 с каждой итерацией. Однако, в отличие от сортировки выбором, если элементы уже упорядочены, внутренний цикл может вообще не выполняться. Кроме того, внутренний цикл будет работать до тех пор, пока не найдет место, где в массив нужно вставить элемент current. При этом в худшем случае все равно упрощается до O(n²). В лучшем случае это O(n), потому что первый цикл for все равно будет выполняться для каждого элемента в массиве, начиная с индекса 1 и далее.

Космическая сложность

Сортировка вставками сортирует на месте, что дает пространственную сложность O(1).

Стабильный алгоритм сортировки

В отличие от сортировки выбором, сортировка вставками является стабильным алгоритмом сортировки. Это означает, что два элемента с одинаковым значением останутся в том порядке, в котором они появились в исходном массиве. Давайте рассмотрим это с нашим массивом учеников, который мы использовали для сортировки выбором.

Мы берем массив студенческих объектов, отсортированных по алфавиту, и сортируем их по оценкам. Желаемое поведение состоит в том, что учащиеся будут отсортированы по классам, а также в алфавитном порядке внутри классов. Например, все ученики первого класса будут отображаться в алфавитном порядке, за ними следуют все ученики второго класса в алфавитном порядке и так далее.

let studentArr = [{name: “Al Cooper” , grade: 4}, {name: “Bobby Tables” , grade: 4}, {name: “Gracie Hopper” , grade: 3}]

Теперь давайте изменим нашу сортировку вставками для обработки этих объектов-студентов:

function insertionSortStudentsByGrade(studentsArray){
    for(let i = 1; i < studentsArray.length; i++){
        let current = studentsArray[i];
        let j = i - 1;
        while(j >= 0 && studentsArray[j]['grade'] >   
        current['grade']){
            studentsArray[j + 1] = studentsArray[j];
            j--;
        }
        studentsArray[j + 1] = current;
    }
    return studentsArray;
}

Если вы пропустите studentArr через эту функцию, вы увидите, что теперь она выглядит так: [{name: “Gracie Hopper”, grade: 3}, {name: “Al Cooper”, grade: 4}, {name: “Bobby Tables”, grade: 4}]

Что является желаемым поведением. В отличие от сортировки выбором, при сортировке вставками Al стоит перед Бобби. Это связано с тем, что первый цикл сортировки вставками увидит, что Ал и Бобби находятся в одном классе, а затем перейдет к Грейси. Оттуда он переместит Бобби на место Грейси, а затем Ала на старое место Бобби, прежде чем поместить Грейси в начало массива. Таким образом, он сохраняет порядок, в котором элементы изначально появлялись.

В заключении…

Хотя сортировка вставками по-прежнему имеет временную сложность O(n²), вы можете быть удивлены, узнав, что она все еще имеет некоторые варианты использования в реальном мире. Сортировка вставками выполняется очень быстро для небольших списков или в случаях, когда список уже почти отсортирован. Таким образом, вы можете увидеть, что другие алгоритмы по умолчанию используют сортировку вставками, если они работают с небольшим размером списка, или вы можете увидеть, как она используется при добавлении элементов в уже отсортированный массив.