Ievietošanas kārtošanas laika sarežģītība

Apsveriet šādus skaitļus:

50 60 30 10 80 70 20 40

Ja šis saraksts ir sakārtots augošā secībā, tas būtu:

10 20 30 40 50 60 70 80

Ja tas ir sakārtots dilstošā secībā, tas būtu:

80 70 60 50 40 30 20 10

Ievietošanas kārtošana ir kārtošanas algoritms, ko izmanto, lai kārtotu sarakstu augošā vai dilstošā secībā. Šis raksts attiecas tikai uz kārtošanu augošā secībā. Kārtošana dilstošā secībā notiek saskaņā ar šajā dokumentā sniegto loģiku. Šī raksta mērķis ir izskaidrot ievietošanas veidu. Programmēšana tiek veikta šajā piemērā C. Ievietošanas kārtošana šeit ir izskaidrota, izmantojot vienu masīvu.

Ievietošanas kārtošanas algoritms

Tiek dots nešķirots saraksts. Mērķis ir kārtot sarakstu augošā secībā, izmantojot to pašu sarakstu. Tiek uzskatīts, ka nešķirota masīva kārtošana, izmantojot to pašu masīvu, ir kārtošana vietā. Šeit tiek izmantota nulles indeksēšana. Darbības ir šādas:

• • Saraksts tiek skenēts no sākuma.
  • Kamēr notiek skenēšana, jebkurš skaitlis, kas ir mazāks par tā priekšgājēju, tiek apmainīts ar tā priekšgājēju.
  • Šī apmaiņa turpinās sarakstā, līdz vairs nav iespējams apmainīt.
  • Kad skenēšana sasniedz beigas, šķirošana ir pabeigta.

Ievietošanas kārtošanas ilustrācija

Runājot par laika sarežģītību, parasti tiek ņemts vērā sliktākais gadījums. Sliktākais iepriekšējā saraksta izkārtojums ir:

80 70 60 50 40 30 20 10

Ir astoņi elementi ar indeksiem no nulles līdz 7.

Ja indekss ir nulle, skenēšana sasniedz 80. Šī ir viena kustība. Šī viena kustība ir operācija. Pagaidām pavisam ir viena operācija (viena kustība, bez salīdzināšanas un bez mijmaiņas). Rezultāts ir:

| 80 70 60 50 40 30 20 10

Pirmajā rādītājā notiek kustība uz 70. 70 tiek salīdzināta ar 80. 70 un 80 tiek apmainīti. Viena kustība ir viena operācija. Viens salīdzinājums ir arī viena operācija. Viena maiņa ir arī viena operācija. Šajā sadaļā ir sniegtas trīs darbības. Pagaidām kopumā ir veiktas četras operācijas (1 + 3 = 4). Rezultāts ir šāds:

70 | 80 60 50 40 30 20 10

Otrajā rādītājā notiek pāreja uz 60. 60 tiek salīdzināta ar 80, pēc tam tiek apmainīti 60 un 80. 60 tiek salīdzināts ar 70, tad 60 un 70 tiek apmainīti. Viena kustība ir viena operācija. Divi salīdzinājumi ir divas darbības. Divi mijmaiņas darījumi ir divas operācijas. Šajā sadaļā ir paredzētas piecas darbības. Pagaidām kopumā ir veiktas deviņas operācijas (4 + 5 = 9). Rezultāts ir šāds:

60 70 | 80 50 40 30 20 10

Trešajā rādītājā notiek pāreja uz 50. 50 tiek salīdzināta ar 80, pēc tam tiek apmainīti 50 un 80. 50 tiek salīdzināti ar 70, tad 50 un 70 tiek apmainīti. 50 tiek salīdzināts ar 60, tad 50 un 60 tiek apmainīti. Viena kustība ir viena operācija. Trīs salīdzinājumi ir trīs darbības. Trīs mijmaiņas darījumi ir trīs operācijas. Šajā sadaļā ir sniegtas septiņas darbības. Pagaidām kopumā ir veiktas sešpadsmit operācijas (9 + 7 = 16). Rezultāts ir šāds:

50 60 70 | 80 40 30 20 10

Pie indeksa ceturtā notiek pāreja uz 40. 40 tiek salīdzināta ar 80, pēc tam tiek apmainīti 40 un 80. 40 tiek salīdzināts ar 70, tad 40 un 70 tiek apmainīti. 40 tiek salīdzināts ar 60, tad 40 un 60 tiek apmainīti. 40 tiek salīdzināts ar 50, tad 40 un 50 tiek apmainīti. Viena kustība ir viena operācija. Četri salīdzinājumi ir četras darbības. Četri mijmaiņas darījumi ir četras operācijas. Šajā sadaļā ir paredzētas deviņas darbības. Pagaidām kopumā ir veiktas divdesmit piecas operācijas (16 + 9 = 25). Rezultāts ir šāds:

40 50 60 70 80 | 30 20 10

Pie indeksa piektā notiek kustība uz 30. 30 tiek salīdzināts ar 80, pēc tam 30 un 80 tiek apmainīti. 30 tiek salīdzināts ar 70, tad 30 un 70 tiek apmainīti. 30 tiek salīdzināts ar 60, tad 30 un 60 tiek apmainīti. 30 tiek salīdzināts ar 50, tad 30 un 50 tiek apmainīti. 30 tiek salīdzināts ar 40, tad 30 un 40 tiek apmainīti. Viena kustība ir viena operācija. Pieci salīdzinājumi ir piecas operācijas. Pieci mijmaiņas darījumi ir piecas operācijas. Šajā sadaļā ir sniegtas vienpadsmit darbības. Pagaidām kopumā ir veiktas trīsdesmit sešas operācijas (25 + 11 = 36). Rezultāts ir šāds:

30 40 50 60 70 80 | 20 10

Indeksā sestais notiek kustība uz 20. 20 tiek salīdzināts ar 80, pēc tam 20 un 80 tiek apmainīti. 20 tiek salīdzināts ar 70, tad 20 un 70 tiek apmainīti. 20 tiek salīdzināts ar 60, tad 20 un 60 tiek apmainīti. 20 tiek salīdzināts ar 50, tad 20 un 50 tiek apmainīti. 20 tiek salīdzināts ar 40, tad 20 un 40 tiek apmainīti. 20 tiek salīdzināts ar 30, tad 20 un 30 tiek apmainīti. Viena kustība ir viena operācija. Seši salīdzinājumi ir sešas operācijas. Seši mijmaiņas darījumi ir sešas operācijas. Šajā sadaļā ir sniegtas trīspadsmit darbības. Pagaidām kopumā ir veiktas četrdesmit deviņas operācijas (36 + 13 = 49). Rezultāts ir šāds:

20 30 40 50 60 70 80 | 10

Pie indeksa septītā notiek pāreja uz 10. 10 tiek salīdzināta ar 80, pēc tam 10 un 80 tiek apmainīti. 10 tiek salīdzināts ar 70, tad 10 un 70 tiek apmainīti. 10 tiek salīdzināts ar 60, tad 10 un 60 tiek apmainīti. 10 tiek salīdzināts ar 50, tad 10 un 50 tiek apmainīti. 10 tiek salīdzināts ar 30, tad 10 un 40 tiek apmainīti. 10 tiek salīdzināts ar 30, tad 10 un 30 tiek apmainīti. 10 tiek salīdzināts ar 20, tad 10 un 20 tiek apmainīti. Viena kustība ir viena operācija. Septiņi salīdzinājumi ir septiņas darbības. Septiņi mijmaiņas darījumi ir septiņas operācijas. Šajā sadaļā ir sniegtas piecpadsmit darbības. Pagaidām kopumā ir veiktas sešdesmit četras operācijas (49 + 15 = 64). Rezultāts ir šāds:

10 20 30 40 50 60 70 80 10 |

Darbs ir padarīts! Tika iesaistītas 64 operācijas.

64 = 8 x 8 = 8 ^divi

Laika sarežģītība ievietošanas kārtošanai

Ja ir n elementi, ko kārtot ar ievietošanas kārtošanu, maksimālais iespējamo darbību skaits būtu n2, kā parādīts iepriekš. Ievietošanas kārtošanas laika sarežģītība ir šāda:

O(n ^divi )

Tas izmanto Big-O apzīmējumu. Big-O apzīmējums sākas ar O ar lielajiem burtiem, kam seko iekavas. Iekavās ir izteiksme par maksimālo iespējamo darbību skaitu.

Kodēšana C valodā

Skenēšanas pašā sākumā pirmais elements nevar mainīt savu pozīciju. Programma būtībā ir šāda:

Funkcijas insertionSort() definīcijā tiek izmantots aprakstītais algoritms. Ņemiet vērā cilpas while nosacījumus. Piemērota C galvenā funkcija šai programmai ir:

Secinājums

Ievietošanas kārtošanas laika sarežģītība ir norādīta šādi:

O(n ^divi )

Lasītājs, iespējams, ir dzirdējis par sliktākā gadījuma laika sarežģītību, vidējo gadījuma laika sarežģītību un labākā gadījuma laika sarežģītību. Šīs ievietošanas kārtošanas laika sarežģītības variācijas ir apskatītas nākamajā mūsu vietnes rakstā.