Рассмотрим следующие числа:
50 60 30 10 80 70 20 40
Если этот список отсортировать в порядке возрастания, это будет:
10 20 30 40 50 60 70 80
Если отсортировать по убыванию, то будет:
80 70 60 50 40 30 20 10
Сортировка вставками — это алгоритм сортировки, который используется для сортировки списка по возрастанию или по убыванию. В этой статье рассматривается только сортировка по возрастанию. Сортировка по убыванию следует той же логике, что и в этом документе. Цель этой статьи — объяснить сортировку вставками. Программирование выполняется в следующем примере на C. Сортировка вставками объясняется здесь с использованием одного массива.
Алгоритм сортировки вставками
Дан несортированный список. Цель состоит в том, чтобы отсортировать список в порядке возрастания, используя тот же список. Сортировка несортированного массива с использованием того же массива называется сортировкой на месте. Здесь используется нулевая индексация. Шаги следующие:
-
- Список сканируется с начала.
- Во время сканирования любое число, меньшее, чем его предшественник, заменяется на его предшественник.
- Этот обмен продолжается по списку до тех пор, пока перестановка становится невозможной.
- Когда сканирование достигает конца, сортировка завершена.
Иллюстрация сортировки вставками
При работе с временной сложностью обычно принимается во внимание наихудший случай. Худшее расположение для предыдущего списка:
80 70 60 50 40 30 20 10
Имеется восемь элементов с индексами от нуля до 7.
При нулевом индексе сканирование доходит до 80. Это одно движение. Одно это движение — операция. Всего пока одна операция (одно перемещение, без сравнения и без обмена). Результат:
| 80 70 60 50 40 30 20 10
По индексу один происходит движение к 70. 70 сравнивается с 80. 70 и 80 меняются местами. Одно движение - одна операция. Одно сравнение — это тоже одна операция. Один своп — это тоже одна операция. В этом разделе представлены три операции. Всего на данный момент выполнено четыре операции (1 + 3 = 4). Результат выглядит следующим образом:
70 | 80 60 50 40 30 20 10
По индексу два происходит движение к 60. 60 сравнивается с 80, затем 60 и 80 меняются местами. 60 сравнивается с 70, затем 60 и 70 меняются местами. Одно движение - одна операция. Два сравнения — это две операции. Два свопа — это две операции. В этом разделе представлены пять операций. Всего на данный момент выполнено девять операций (4 + 5 = 9). Результат выглядит следующим образом:
60 70 | 80 50 40 30 20 10
По индексу три происходит движение к 50. 50 сравнивается с 80, затем 50 и 80 меняются местами. 50 сравнивается с 70, затем 50 и 70 меняются местами. 50 сравнивается с 60, затем 50 и 60 меняются местами. Одно движение - одна операция. Три сравнения — это три операции. Три свопа — это три операции. В этом разделе представлены семь операций. Всего на данный момент выполнено шестнадцать операций (9 + 7 = 16). Результат выглядит следующим образом:
50 60 70 | 80 40 30 20 10
По индексу четыре происходит движение к 40. 40 сравнивается с 80, затем 40 и 80 меняются местами. 40 сравнивается с 70, затем 40 и 70 меняются местами. 40 сравнивается с 60, затем 40 и 60 меняются местами. 40 сравнивается с 50, затем 40 и 50 меняются местами. Одно движение - одна операция. Четыре сравнения — это четыре операции. Четыре свопа — это четыре операции. В этом разделе представлены девять операций. Всего на данный момент выполнено двадцать пять операций (16 + 9 = 25). Результат выглядит следующим образом:
40 50 60 70 80 | 30 20 10
По индексу пять происходит движение к 30. 30 сравнивается с 80, затем 30 и 80 меняются местами. 30 сравнивается с 70, затем 30 и 70 меняются местами. 30 сравнивается с 60, затем 30 и 60 меняются местами. 30 сравнивается с 50, затем 30 и 50 меняются местами. 30 сравнивается с 40, затем 30 и 40 меняются местами. Одно движение - одна операция. Пять сравнений — это пять операций. Пять свопов — это пять операций. В этом разделе представлены одиннадцать операций. Всего на данный момент выполнено тридцать шесть операций (25 + 11 = 36). Результат выглядит следующим образом:
30 40 50 60 70 80 | 20 10
По индексу шесть происходит движение к 20. 20 сравнивается с 80, затем 20 и 80 меняются местами. 20 сравнивается с 70, затем 20 и 70 меняются местами. 20 сравнивается с 60, затем 20 и 60 меняются местами. 20 сравнивается с 50, затем 20 и 50 меняются местами. 20 сравнивается с 40, затем 20 и 40 меняются местами. 20 сравнивается с 30, затем 20 и 30 меняются местами. Одно движение - одна операция. Шесть сравнений — это шесть операций. Шесть свопов — это шесть операций. В этом разделе представлены тринадцать операций. Всего пока выполнено сорок девять операций (36 + 13 = 49). Результат выглядит следующим образом:
20 30 40 50 60 70 80 | 10
По индексу семь происходит движение к 10. 10 сравнивается с 80, затем 10 и 80 меняются местами. 10 сравнивается с 70, затем 10 и 70 меняются местами. 10 сравнивается с 60, затем 10 и 60 меняются местами. 10 сравнивается с 50, затем 10 и 50 меняются местами. 10 сравнивается с 30, затем 10 и 40 меняются местами. 10 сравнивается с 30, затем 10 и 30 меняются местами. 10 сравнивается с 20, затем 10 и 20 меняются местами. Одно движение - одна операция. Семь сравнений — это семь операций. Семь свопов — это семь операций. В этом разделе представлены пятнадцать операций. Всего на данный момент выполнено шестьдесят четыре операции (49 + 15 = 64). Результат выглядит следующим образом:
10 20 30 40 50 60 70 80 10 |
Работа сделана! Было проведено 64 операции.
64 = 8 х 8 = 8 два
Временная сложность для сортировки вставками
Если есть n элементов для сортировки с помощью сортировки вставками, максимальное количество возможных операций будет n2, как показано ранее. Сложность времени сортировки вставками:
На два )
Это использует нотацию Big-O. Обозначение Big-O начинается с O в верхнем регистре, за которым следуют круглые скобки. В скобках указано максимально возможное количество операций.
Кодирование на C
В самом начале сканирования первый элемент не может изменить свое положение. Программа по сути следующая:
#includeпустая вставкаСортировка ( инт А [ ] , целое N ) {
за ( инт я знак равно 0 ; я < Н; я++ ) {
интервал j = я;
пока ( А [ Дж ] < А [ j- 1 ] && j- 1 > знак равно 0 ) {
инт темп = А [ Дж ] ; А [ Дж ] = А [ j- 1 ] ; А [ j- 1 ] = температура; // менять
ж--;
}
}
}
В определении функции insertionSort() используется описанный алгоритм. Обратите внимание на условия цикла while. Подходящей основной функцией C для этой программы является:
{
инт п = 8 ;
инт А [ ] знак равно { 50 , 60 , 30 , 10 , 80 , 70 , 20 , 40 } ;
вставкаСортировка ( А, н ) ;
за ( инт я знак равно 0 ; я < н; я++ ) {
printf ( '%i' , А [ я ] ) ;
}
printf ( ' \n ' ) ;
возвращаться 0 ;
}
Вывод
Временная сложность сортировки вставками определяется как:
На два )
Читатель, возможно, слышал о временной сложности в худшем случае, временной сложности в среднем и временной сложности в лучшем случае. Эти варианты временной сложности сортировки вставками обсуждаются в следующей статье на нашем веб-сайте.