Помислете за следните числа:
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 x 8 = 8 две
Времева сложност за сортиране чрез вмъкване
Ако има n елемента за сортиране с Insertion Sort, максималният брой възможни операции ще бъде n2, както беше показано по-рано. Сложността на времето за сортиране на вмъкване е:
На две )
Това използва нотацията Big-O. Нотацията Big-O започва с O в главни букви, последвано от скоби. Вътре в скобите е изразът за максималния възможен брой операции.
Кодиране в C
В самото начало на сканирането първият елемент не може да промени позицията си. Програмата по същество е следната:
#includeпразно вмъкванеСортиране ( int A [ ] , int N ) {
за ( вътр аз = 0 ; аз < Н; i++ ) {
int j = i;
докато ( А [ й ] < А [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ й ] ; А [ й ] = А [ j- 1 ] ; А [ j- 1 ] = температура; // размяна
j--;
}
}
}
Дефиницията на функцията insertionSort() използва алгоритъма, както е описано. Обърнете внимание на условията за цикъла while. Подходяща C основна функция за тази програма е:
{
int n = 8 ;
int A [ ] = { петдесет , 60 , 30 , 10 , 80 , 70 , двадесет , 40 } ;
вмъкванеСортиране ( A, n ) ;
за ( вътр аз = 0 ; аз < н; i++ ) {
printf ( '%i' , А [ аз ] ) ;
}
printf ( ' \н ' ) ;
връщане 0 ;
}
Заключение
Времевата сложност за сортиране чрез вмъкване се дава като:
На две )
Читателят може да е чувал за времева сложност в по-лош случай, времева сложност в среден случай и времева сложност в най-добър случай. Тези варианти на времевата сложност на сортиране при вмъкване са обсъдени в следващата статия на нашия уебсайт.