Времева сложност на сортиране на вмъкване

Помислете за следните числа:

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

В самото начало на сканирането първият елемент не може да промени позицията си. Програмата по същество е следната:

Дефиницията на функцията insertionSort() използва алгоритъма, както е описано. Обърнете внимание на условията за цикъла while. Подходяща C основна функция за тази програма е:

Заключение

Времевата сложност за сортиране чрез вмъкване се дава като:

На ^две )

Читателят може да е чувал за времева сложност в по-лош случай, времева сложност в среден случай и времева сложност в най-добър случай. Тези варианти на времевата сложност на сортиране при вмъкване са обсъдени в следващата статия на нашия уебсайт.