Введение
Сортировка вставками — один из самых простых алгоритмов, используемых для сортировки массивов. Самым большим преимуществом сортировки вставками является то, что ее легко реализовать, однако она может быть весьма эффективной для небольших объемов данных и частично отсортированных массивов.
Распространенной аналогией для описания того, как работает этот алгоритм, является то, как мы, люди, сортируем карты в руках. Как мы это делаем, мы сохраняем отсортированные карты слева, а несортированные карты справа (по крайней мере, для правшей), и мы перебираем карты справа. Для каждой карты мы сравниваем ее с картами слева и вставляем в правильное положение.
Алгоритм
Алгоритм такой (сортировка по возрастанию):
- Начните со второго элемента (arr[1]) и сравните его с первым элементом (arr[0]).
- Если arr[1] меньше, чем arr[0], поменяйте их местами.
- Перейдите к третьему элементу (arr[2]) и сравните его с arr[1]. Если arr[2] меньше, замените его на arr[1]. Затем сравните arr[1] с arr[0] и при необходимости поменяйте местами.
- Повторите этот процесс для всех последующих элементов, пока весь массив не будет отсортирован.
Иллюстрация
Step 1 arr = [5, 2, 4, 6, 1] arr[0] = 5 arr[1] = 2 Step 2 arr[0] > arr[1] --> True. Found unsorted values. Swapping them arr = [2, 5, 4, 6, 1] Step 3 arr = [2, 5, 4, 6, 1] arr[1] = 5 arr[2] = 4 arr[1] > arr[2] --> True. Found unsorted values. Swapping them Comparing the previous pair: arr = [2, 4, 5, 6, 1] arr[0] = 2 arr[1] = 4 arr[0] > arr[1] --> False. Step 4 arr = [2, 4, 5, 6, 1] arr[2] = 5 arr[3] = 6 arr[2] > arr[3] --> False. arr = [2, 4, 5, 6, 1] arr[3] = 6 arr[4] = 1 arr[3] > arr[4] --> True. Found unsorted values. Swapping them. Comparing the previous pair: arr = [2, 4, 5, 1, 6] arr[2] = 5 arr[3] = 1 arr[2] > arr[3] --> True. Found unsorted values. Swapping them. Comparing the previous pair: arr = [2, 4, 1, 5, 6] arr[1] = 4 arr[2] = 1 arr[1] > arr[2] --> True. Found unsorted values. Swapping them. Comparing the previous pair: arr = [2, 1, 4, 5, 6] arr[0] = 2 arr[1] = 1 arr[0] > arr[1] --> True. Found unsorted values. Swapping them. Done. arr = [1, 2, 4, 5, 6]
Как мы видим, на каждой итерации мы «перемещаем» наименьшее значение в правильное место в массиве.
Псевдокод
for j=1 to arr.Length:
key = arr[j] # Set current index
i = j - 1 # Set previous index
# Found unsorted values
while arr[i] > key and i >= 0:
arr[i+1] = arr[i] # Swapping them
i = i - 1 # Comparing the previous pair
arr[i+1] = key # Inserting the key in the correct position
Код
питон
def insertion_sort(arr):
for j in range(1, len(arr)):
key = arr[j]
i = j - 1
while arr[i] > key and i >= 0:
arr[i+1] = arr[i]
i -= 1
arr[i+1] = key
return arr
arr = [5, 2, 4, 6, 1]
sorted_array = insertion_sort(arr)
print(sorted_array)
# [1, 2, 4, 5, 6]
C
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5 /*Array length*/
void insertion_sort(int arr[]);
int main(void)
{
/*Initialize variables*/
int i;
int arr[MAXSIZE] = {5, 2, 4, 6, 1};
/*Apply insertion sort*/
insertion_sort(arr);
/*Print results*/
for (i = 0; i < MAXSIZE; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
/*return stats*/
return 0;
}
void insertion_sort(int arr[])
{
int i, j, key;
key = 0;
for (j = 1; j < MAXSIZE; j++)
{
key = arr[j]; /*Set current index*/
i = j - 1; /*Set previous index*/
/*Found unsorted values*/
while(arr[i] > key && i >= 0)
{
arr[i+1] = arr[i]; /*Swapping them*/
i = i - 1; /*Comparing the previous pair*/
}
arr[i+1] = key; /*Inserting the key in the correct position*/
}
}
gcc insertion_sort.c -o insertion_sort
./insertion_sort
# [1, 2, 4, 5, 6]
Обсуждение
Время выполнения — O(n²)
В худшем случае массив полностью отсортирован, но в порядке убывания. В этом случае внешний цикл будет выполняться n раз, и для каждой итерации будет выполняться внутренний цикл (n-j+1).
Следовательно, общее количество итераций равно n * (n-j+1), что равно O(n²).
В лучшем случае массив уже отсортирован, и нам нужно выполнить итерацию по массиву только один раз, поэтому O(n).
Сложность пространства — O(1)
Поскольку мы сортируем массив на месте и отслеживаем только текущий и предыдущий индексы, независимо от размера входных данных, объемная сложность составляет O(1).
Преимущества
- Легко реализовать.
- Стабильный
- Эффективен при небольшом количестве элементов.
- Эффективен, когда элементы почти отсортированы.
- Сортируйте на месте, таким образом резервируя ресурсы.
Доказательство правильности
Доказать правильность алгоритма можно по индукции.
Предположим, что алгоритм верен для первых j-1 элементов массива (т.е. мы предполагаем, что arr[0..j-1] отсортирован). Докажем, что алгоритм корректен для первых j элементов массива.
В начале j-й итерации алгоритм будет сравнивать j-й элемент с j-1-м элементом. Мы можем разделить это на два случая:
- arr[j] меньше, чем arr[j-1]:
- В этом случае алгоритм будет сравнивать arr[j] с arr[j-2], arr[j-3], …, arr[0] до тех пор, пока не найдет значение, меньшее, чем arr[j], и вставит arr [j] в правильном положении.
- Все остальные элементы будут смещены вправо.
- Следовательно, arr[0..j] будет отсортирован.
2. arr[j] больше, чем arr[j-1]:
- По предположению индукции мы знаем, что arr[0..j-1] отсортировано, и если arr[j] больше, чем arr[j-1], то получаем, что arr[0..j] отсортировано .
Поскольку алгоритм корректен для первых j элементов массива, и мы предполагаем, что он корректен для первых j-1 элементов массива, мы можем сделать вывод, что алгоритм корректен для первых j+1 элементов массива .
Следовательно, алгоритм корректен для всех элементов массива.
