Введение в алгоритм сортировки вставкой

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

Алгоритм начинается с первого элемента списка как отсортированного подсписка. Затем он сравнивает следующее число с первым. Если он больше, то он вставляется в первый индекс. В противном случае он остается в своем индексе.

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

Более пристальный взгляд на сортировку вставкой

Приведенное выше описание могло не иметь для вас смысла. Пример должен помочь вам лучше понять.

Предположим, у вас есть список: [39, 6, 2, 51, 30, 42, 7].

Алгоритм определяет 39 как первое значение отсортированного подсписка. Затем оценка переходит на вторую позицию.

Связанный: Динамическое программирование: примеры, общие проблемы и решения

Затем 6 сравнивается с 39. Поскольку 6 меньше 39, 6 вставляется в первую позицию, а 39 – во вторую. Новый порядок в списке после первого прохода:

[6, 39, 2, 51, 30, 42, 7]

Теперь оценка переходит на третью позицию. 2 сравнивается с двумя последними числами и затем вставляется в правильную позицию. Новый порядок в списке после второго прохода:

[2, 6, 39, 51, 30, 42, 7]

Для третьего прохода порядок списка следующий:

[2, 6, 39, 51, 30, 42, 7]

Процесс повторяется до тех пор, пока не будет отсортирован весь список.

См. Диаграмму ниже, на которой резюмируются эти операции:

Алгоритм анализа

Временная сложность сортировки вставкой составляет O (n ² ), как и сортировка пузырьков . Количество сравнений в наихудшем сценарии – это сумма всех целых чисел от 1 до (n-1), дающая квадратичную сумму.

Реализация кода

В приведенном ниже коде Python и Java показано, как можно реализовать метод сортировки вставкой.

Python:

 def insertionSort(mylist):
 for step in range(1, len(mylist)):
 current_element = mylist[step]
 position = step
 while position > 0 and mylist[position - 1] > current_element:
 mylist[position] = mylist[position - 1]
 position = position - 1
 mylist[position] = current_element

Джава:

 void insertionSort(int[] myarray) {
 int n = myarray.length;
 for (int x = 1; x < n; x++) {
 int key = myarray[x];
 int y = x-1;
 while ( (y > -1) && ( myarray [y] > key ) ) {
 myarray [y+1] = myarray [y];
 y--;
 }
 myarray[y+1] = key;
 }
 }

Лучшее кодирование с помощью псевдокода

Приведенные выше примеры кода были даны без какого-либо псевдокода, на который вы можете ссылаться, чтобы написать этот алгоритм на других языках. Большинство программистов (включая автора) любят подбегать к клавиатуре после того, как им говорят «шепотом» о том, как работает программа.

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