Časovna zapletenost razvrščanja vstavljanja

Upoštevajte naslednje številke:

50 60 30 10 80 70 20 40

Če je ta seznam razvrščen v naraščajočem vrstnem redu, bi bil:

10 20 30 40 50 60 70 80

Če je razvrščeno po padajočem vrstnem redu, bi bilo:

80 70 60 50 40 30 20 10

Razvrščanje z vstavljanjem je algoritem za razvrščanje, ki se uporablja za razvrščanje seznama v naraščajočem ali padajočem vrstnem redu. Ta članek obravnava samo razvrščanje v naraščajočem vrstnem redu. Razvrščanje v padajočem vrstnem redu sledi isti logiki, ki je navedena v tem dokumentu. Namen tega članka je razložiti vrsto vstavljanja. Programiranje poteka v naslednjem primeru v C. Razvrščanje vstavljanja je tukaj razloženo z uporabo enega polja.

Algoritem za razvrščanje z vstavljanjem

Podan je nerazvrščen seznam. Cilj je razvrstiti seznam v naraščajočem vrstnem redu z uporabo istega seznama. Razvrščanje nerazvrščene matrike z uporabo iste matrike je razvrščanje na mestu. Tu se uporablja indeksiranje na podlagi nič. Koraki so naslednji:

• • Seznam se skenira od začetka.
  • Med skeniranjem se vsako število, ki je manjše od njegovega predhodnika, zamenja s svojim predhodnikom.
  • Ta zamenjava se nadaljuje po seznamu, dokler zamenjava ni več mogoča.
  • Ko je skeniranje končano, je razvrščanje končano.

Ilustracija razvrščanja vstavljanja

Pri obravnavanju časovne kompleksnosti se običajno upošteva najslabši primer. Najslabša ureditev za prejšnji seznam je:

80 70 60 50 40 30 20 10

Obstaja osem elementov z indeksi od nič do 7.

Pri indeksu nič gre skeniranje na 80. To je en premik. To eno gibanje je operacija. Doslej je skupno ena operacija (en premik, brez primerjave in brez zamenjave). Rezultat je:

| 80 70 60 50 40 30 20 10

Pri indeksu ena je premik na 70. 70 se primerja z 80. 70 in 80 se zamenjata. En gib je ena operacija. Ena primerjava je tudi ena operacija. Ena zamenjava je tudi ena operacija. Ta razdelek ponuja tri operacije. Skupaj so do sedaj štiri operacije (1 + 3 = 4). Rezultat je naslednji:

70 | 80 60 50 40 30 20 10

Pri indeksu dva pride do premika na 60. 60 se primerja z 80, nato se 60 in 80 zamenjata. 60 primerjamo s 70, nato 60 in 70 zamenjamo. En gib je ena operacija. Dve primerjavi sta dve operaciji. Dve zamenjavi sta dve operaciji. V tem razdelku je pet operacij. Skupaj je do sedaj devet operacij (4 + 5 = 9). Rezultat je naslednji:

60 70 | 80 50 40 30 20 10

Pri indeksu tri je premik na 50. 50 se primerja z 80, nato se 50 in 80 zamenjata. 50 primerjamo s 70, nato 50 in 70 zamenjamo. 50 primerjamo s 60, nato 50 in 60 zamenjamo. En gib je ena operacija. Tri primerjave so tri operacije. Tri zamenjave so tri operacije. V tem razdelku je sedem operacij. Skupaj je do sedaj šestnajst operacij (9 + 7 = 16). Rezultat je naslednji:

50 60 70 | 80 40 30 20 10

Pri indeksu štiri pride do premika na 40. 40 se primerja z 80, nato se 40 in 80 zamenjata. 40 primerjamo s 70, nato 40 in 70 zamenjamo. 40 primerjamo s 60, nato 40 in 60 zamenjamo. 40 primerjamo s 50, nato 40 in 50 zamenjamo. En gib je ena operacija. Štiri primerjave so štiri operacije. Štiri zamenjave so štiri operacije. V tem razdelku je devet operacij. Skupaj je do sedaj petindvajset operacij (16 + 9 = 25). Rezultat je naslednji:

40 50 60 70 80 | 30 20 10

Pri indeksu pet je premik na 30. 30 se primerja z 80, nato se 30 in 80 zamenjata. 30 primerjamo s 70, nato 30 in 70 zamenjamo. 30 primerjamo s 60, nato 30 in 60 zamenjamo. 30 primerjamo s 50, nato 30 in 50 zamenjamo. 30 primerjamo s 40, nato 30 in 40 zamenjamo. En gib je ena operacija. Pet primerjav je pet operacij. Pet zamenjav je pet operacij. Ta razdelek ponuja enajst operacij. Skupaj je do sedaj šestintrideset operacij (25 + 11 = 36). Rezultat je naslednji:

30 40 50 60 70 80 | 20 10

Pri indeksu šest je premik na 20. 20 se primerja z 80, nato se 20 in 80 zamenjata. 20 primerjamo s 70, nato 20 in 70 zamenjamo. 20 primerjamo s 60, nato 20 in 60 zamenjamo. 20 primerjamo s 50, nato 20 in 50 zamenjamo. 20 primerjamo s 40, nato 20 in 40 zamenjamo. 20 primerjamo s 30, nato 20 in 30 zamenjamo. En gib je ena operacija. Šest primerjav je šest operacij. Šest zamenjav je šest operacij. Ta razdelek ponuja trinajst operacij. Skupaj je do sedaj devetinštirideset operacij (36 + 13 = 49). Rezultat je naslednji:

20 30 40 50 60 70 80 | 10

Pri indeksu sedem je premik na 10. 10 se primerja z 80, nato se 10 in 80 zamenjata. 10 primerjamo s 70, nato 10 in 70 zamenjamo. 10 primerjamo s 60, nato 10 in 60 zamenjamo. 10 primerjamo s 50, nato 10 in 50 zamenjamo. 10 primerjamo s 30, nato 10 in 40 zamenjamo. 10 primerjamo s 30, nato 10 in 30 zamenjamo. 10 primerjamo z 20, nato 10 in 20 zamenjamo. En gib je ena operacija. Sedem primerjav je sedem operacij. Sedem zamenjav je sedem operacij. Ta razdelek ponuja petnajst operacij. Skupaj je do sedaj štiriinšestdeset operacij (49 + 15 = 64). Rezultat je naslednji:

10 20 30 40 50 60 70 80 10 |

Delo je opravljeno! Vključenih je bilo 64 operacij.

64 = 8 x 8 = 8 ^dva

Časovna zapletenost za razvrščanje z vstavljanjem

Če obstaja n elementov za razvrščanje z Razvrščanjem z vstavljanjem, bi bilo največje možno število operacij n2, kot je prikazano prej. Zapletenost časa razvrščanja vstavljanja je:

O(n ^dva )

To uporablja zapis Big-O. Zapis Big-O se začne z O v velikih črkah, ki mu sledijo oklepaji. Znotraj oklepajev je izraz za največje možno število operacij.

Kodiranje v C

Na samem začetku skeniranja prvi element ne more spremeniti svojega položaja. Program je v bistvu sledeč:

Definicija funkcije insertionSort() uporablja opisani algoritem. Upoštevajte pogoje za zanko while. Primerna glavna funkcija C za ta program je:

Zaključek

Časovna kompleksnost za razvrščanje z vstavljanjem je podana kot:

O(n ^dva )

Bralec je morda že slišal za časovno zapletenost v slabšem primeru, povprečno časovno zapletenost in najboljšo časovno zapletenost. Te različice časovne zapletenosti razvrščanja vstavljanja so obravnavane v naslednjem članku na našem spletnem mestu.