Вступление

В этой статье мы объясним, в чем заключается идея сортировки вставкой, и реализуем ее на JavaScript.

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

Стабильный алгоритм сортировки - это алгоритм, в котором два объекта с одинаковыми ключами появляются в отсортированном выводе в том же порядке, что и во входном массиве для сортировки.

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

Алгоритм на месте - это алгоритм, который не использует дополнительную память или структуры данных, перезаписывая исходные ячейки памяти элементов во входном массиве или списке.

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

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

Он редко используется в качестве отдельного алгоритма - вы обычно используете алгоритм быстрой сортировки, такой как Quicksort, и завершаете последние «свободные концы» с помощью сортировки вставкой, поскольку он очень эффективен для этой задачи.

Сортировка вставкой

Идею сортировки вставками часто сравнивают с тем, как люди сортируют карты во время игры в Рамми.

В этой карточной игре дилер раздает карты каждому игроку. Затем игроки берут данные им карты одну за другой, сортируя их в руке в порядке возрастания, вставляя каждую карту на свое место.

В течение всего этого процесса игроки держат в руках одну отсортированную стопку карт, в то время как несортированная стопка, из которой они берут новые карты, находится перед ними.

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

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

Вот визуальное представление того, как работает сортировка вставкой:

{.ezlazyload}

Реализация сортировки вставкой

Теперь, когда мы понимаем идею сортировки вставкой, мы можем перейти к реализации:

 function insertionSort(inputArr) { 
 let n = inputArr.length; 
 for (let i = 1; i < n; i++) { 
 // Choosing the first element in our unsorted subarray 
 let current = inputArr[i]; 
 // The last element of our sorted subarray 
 let j = i-1; 
 while ((j > -1) && (current < inputArr[j])) { 
 inputArr[j+1] = inputArr[j]; 
 j--; 
 } 
 inputArr[j+1] = current; 
 } 
 return inputArr; 
 } 

Итерация начинается со второго элемента. Считаем отсортированным по умолчанию первый элемент. Для каждой итерации мы отслеживаем current элемент. Каждый current элемент будет первым элементом несортированного массива - и каждый элемент перед ним будет принадлежать отсортированному массиву.

Через в while цикла, мы проходим отсортированный массив и сдвиг элементы вправо, открывая пространство для current элемента должны быть вставлено.

Как только мы найдем для него подходящее место, current элемент вставляется во вновь открытый слот. Этот процесс повторяется для каждой итерации, пока массив не будет отсортирован.

Теперь давайте заполним массив и вызовем наш алгоритм сортировки:

 let inputArr = [5, 2, 4, 6, 1, 3]; 
 insertionSort(inputArr); 
 console.log(inputArr); 

Результатом этого массива будет:

 (6) [1, 2, 3, 4, 5, 6] 

Давайте рассмотрим этот пример шаг за шагом:

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

Отсортированный массив: 5
Несортированный массив: 2, 4, 6, 1, 3

• Первый элемент в нашем несортированном массиве - 2.
• 2 <5, поэтому мы перемещаем 5 на одну позицию вправо.

Отсортированный массив: _, 5

• 2 помещается в правильное место.

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

Отсортированный массив: 2, 5
Несортированный массив: 4, 6, 1, 3

• Первый элемент в нашем несортированном массиве - 4.
• 4 <5, поэтому мы перемещаем 5 на одну позицию вправо.

Отсортированный массив: 2, _, 5

• 4! <2, поэтому мы не перемещаем 2.
• 4 помещается в правильное место.

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

Отсортированный массив: 2, 4, 5
Несортированный массив: 6, 1, 3

• Первый элемент в нашем несортированном массиве - 6.
• 6! <5, поэтому мы не перемещаем 5.

Отсортированный массив: 2, 4, 5

• 6 помещается на свое место.

Это повторяется до тех пор, пока нас не встретит отсортированный массив: 1, 2, 3, 4, 5, 6 .

Мы можем заметить инвариант в каждой из этих итераций. Для k-th итерации нашего цикла интервал [0,k] гарантированно будет отсортирован.

Сравнение времени

Лучшее время работы сортировки вставкой - линейное, и мы получаем его, если наш входной массив уже отсортирован. Это означает, что сортировка вставкой творит чудеса, когда дело доходит до проверки того, отсортирован ли массив.

Однако наихудшая и средняя временная сложность - O (n ^2^ ), что довольно плохо для алгоритма сортировки, особенно когда он применяется к массивам или спискам большего размера. В этом случае быстрая сортировка или сортировка слиянием со сложностью O (nlogn) были бы гораздо лучшим выбором.

С другой стороны, будучи одним из самых быстрых алгоритмов квадратичной сортировки, сортировка вставкой обычно превосходит пузырьковую сортировку , сортировку Gnome и сортировку по выбору . В дополнение к этому, когда размер нашего входного массива очень мал (10-20 элементов), сортировка вставкой может даже превзойти быструю сортировку и сортировку слиянием.

Вот почему JavaScript, несмотря на использование Quicksort (в Chrome) или Merge Sort (в Mozilla) в качестве основного алгоритма сортировки, также использует сортировку вставкой для небольших коллекций - и после того, как Quicksort / Merge Sort выполнила основную часть работы.

Заключение

Сортировка вставкой - это простой, стабильный алгоритм сортировки по месту.

Несмотря на то, что квадратичная сложность занимает довольно много времени, это очень полезно, когда входной массив имеет небольшой размер. В этом случае он даже превосходит наиболее часто используемые алгоритмы «разделяй и властвуй», поэтому JavaScript использует комбинацию сортировки вставкой и сортировки слиянием или быстрой сортировки при использовании встроенных функций сортировки.

Когда дело доходит до массивов большего размера, он превосходит большинство других алгоритмов квадратичной сортировки, включая пузырьковую сортировку, сортировку Gnome, а также сортировку по выбору.