Mõelge järgmistele numbritele:
50 60 30 10 80 70 20 40
Kui see loend on järjestatud kasvavas järjekorras, oleks see järgmine:
10 20 30 40 50 60 70 80
Kui see on sorteeritud kahanevas järjekorras, oleks see:
80 70 60 50 40 30 20 10
Sisestamise sortimine on sortimisalgoritm, mida kasutatakse loendi sortimiseks kasvavas või kahanevas järjekorras. See artikkel käsitleb ainult kasvavas järjekorras sortimist. Sorteerimine kahanevas järjekorras järgib selles dokumendis toodud loogikat. Selle artikli eesmärk on selgitada sisestussortimist. Programmeerimine toimub järgmises näites C-s. Sisestussortimist selgitatakse siin ühe massiivi abil.
Sisestamise sortimise algoritm
Esitatakse sortimata loend. Eesmärk on järjestada loend sama loendi abil kasvavas järjekorras. Sorteerimata massiivi sortimine sama massiivi abil on paigas sortimine. Siin kasutatakse nullipõhist indekseerimist. Toimingud on järgmised.
-
- Loendit skannitakse algusest peale.
- Skannimise ajal vahetatakse eelkäijast väiksemad numbrid eelkäijaga.
- See vahetus jätkub loendis, kuni vahetamine pole enam võimalik.
- Kui skannimine jõuab lõpuni, on sortimine lõppenud.
Sisestuse sortimise illustratsioon
Ajalise keerukuse käsitlemisel võetakse tavaliselt arvesse kõige halvemat juhtumit. Eelmise loendi halvim korraldus on:
80 70 60 50 40 30 20 10
Seal on kaheksa elementi indeksiga nullist 7-ni.
Nullindeksi korral läheb skannimine 80-ni. See on üks liigutus. See üks liigutus on operatsioon. Kokku on seni tehtud üks operatsioon (üks liigutus, võrdlus puudub ja vahetust pole). Tulemuseks on:
| 80 70 60 50 40 30 20 10
Esimesel indeksil on liikumine 70-ni. 70 võrreldakse 80-ga. 70 ja 80 vahetatakse. Üks liigutus on üks operatsioon. Üks võrdlus on ka üks operatsioon. Üks vahetus on ka üks toiming. Selles jaotises on kolm toimingut. Kokku on seni tehtud neli operatsiooni (1 + 3 = 4). Tulemus on järgmine:
70 | 80 60 50 40 30 20 10
Indeksi 2 juures liigutakse 60-ni. 60 võrreldakse 80-ga, seejärel vahetatakse 60 ja 80. 60 võrreldakse 70-ga, seejärel vahetatakse 60 ja 70. Üks liigutus on üks operatsioon. Kaks võrdlust on kaks toimingut. Kaks vahetust on kaks toimingut. Selles jaotises on viis toimingut. Kokku on seni tehtud üheksa operatsiooni (4 + 5 = 9). Tulemus on järgmine:
60 70 | 80 50 40 30 20 10
Kolmandal indeksil liigutakse 50-ni. 50 võrreldakse 80-ga, seejärel vahetatakse 50 ja 80. 50 võrreldakse 70-ga, seejärel vahetatakse 50 ja 70. 50 võrreldakse 60-ga, seejärel vahetatakse 50 ja 60. Üks liigutus on üks operatsioon. Kolm võrdlust on kolm toimingut. Kolm vahetust on kolm toimingut. Selles jaotises on seitse toimingut. Kokku on seni tehtud kuusteist operatsiooni (9 + 7 = 16). Tulemus on järgmine:
50 60 70 | 80 40 30 20 10
Neljas indeksis liigutakse 40-ni. 40 võrreldakse 80-ga, seejärel vahetatakse 40 ja 80. 40 võrreldakse 70-ga, seejärel vahetatakse 40 ja 70. 40 võrreldakse 60-ga, seejärel vahetatakse 40 ja 60. 40 võrreldakse 50-ga, seejärel vahetatakse 40 ja 50. Üks liigutus on üks operatsioon. Neli võrdlust on neli operatsiooni. Neli vahetust on neli toimingut. See jaotis sisaldab üheksa toimingut. Kokku on seni tehtud kakskümmend viis operatsiooni (16 + 9 = 25). Tulemus on järgmine:
40 50 60 70 80 | 30 20 10
Viies indeksis liigub 30. 30 võrreldakse 80-ga, seejärel vahetatakse 30 ja 80. 30 võrreldakse 70-ga, seejärel vahetatakse 30 ja 70. 30 võrreldakse 60-ga, seejärel vahetatakse 30 ja 60. 30 võrreldakse 50-ga, seejärel vahetatakse 30 ja 50. 30 võrreldakse 40-ga, seejärel vahetatakse 30 ja 40. Üks liigutus on üks operatsioon. Viis võrdlust on viis operatsiooni. Viis vahetust on viis toimingut. Selles jaotises on üksteist toimingut. Kokku on seni tehtud kolmkümmend kuus operatsiooni (25 + 11 = 36). Tulemus on järgmine:
30 40 50 60 70 80 | 20 10
Indeksi kuue juures liigub 20. 20 võrreldakse 80-ga, seejärel 20 ja 80 vahetatakse. 20 võrreldakse 70-ga, seejärel vahetatakse 20 ja 70. 20 võrreldakse 60-ga, seejärel 20 ja 60 vahetatakse. 20 võrreldakse 50-ga, seejärel 20 ja 50 vahetatakse. 20 võrreldakse 40-ga, seejärel 20 ja 40 vahetatakse. 20 võrreldakse 30-ga, seejärel 20 ja 30 vahetatakse. Üks liigutus on üks operatsioon. Kuus võrdlust on kuus operatsiooni. Kuus vahetustehingut on kuus operatsiooni. Selles jaotises on kolmteist toimingut. Kokku on seni tehtud nelikümmend üheksa operatsiooni (36 + 13 = 49). Tulemus on järgmine:
20 30 40 50 60 70 80 | 10
Seitsmendal indeksil liigutakse 10-ni. 10 võrreldakse 80-ga, seejärel vahetatakse 10 ja 80. 10 võrreldakse 70-ga, seejärel vahetatakse 10 ja 70. 10 võrreldakse 60-ga, seejärel vahetatakse 10 ja 60. 10 võrreldakse 50-ga, seejärel vahetatakse 10 ja 50. 10 võrreldakse 30-ga, seejärel vahetatakse 10 ja 40. 10 võrreldakse 30-ga, seejärel vahetatakse 10 ja 30. 10 võrreldakse 20-ga, seejärel vahetatakse 10 ja 20. Üks liigutus on üks operatsioon. Seitse võrdlust on seitse toimingut. Seitse vahetustehingut on seitse operatsiooni. See jaotis sisaldab viisteist toimingut. Kokku on seni tehtud kuuskümmend neli operatsiooni (49 + 15 = 64). Tulemus on järgmine:
10 20 30 40 50 60 70 80 10 |
Töö on tehtud! Kaasatud oli 64 operatsiooni.
64 = 8 x 8 = 8 kaks
Sisestuse sortimise aja keerukus
Kui sisestussortimisega sortimiseks on n elementi, on võimalike toimingute maksimaalne arv n2, nagu eelnevalt näidatud. Sisestuse sortimise aja keerukus on järgmine:
Peal kaks )
See kasutab Big-O tähistust. Big-O tähistus algab O-ga suurtähtedega, millele järgnevad sulud. Sulgude sees on avaldis maksimaalse võimaliku arvu toimingute kohta.
Kodeerimine C-s
Skaneerimise alguses ei saa esimene element oma asukohta muuta. Programm on sisuliselt järgmine:
#includetühine sisestusSort ( int A [ ] , int N ) {
jaoks ( int i = 0 ; i < N; i++ ) {
int j = i;
samal ajal ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
sisetemperatuur = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temp; // vahetus
j--;
}
}
}
Funktsiooni insertionSort() definitsioon kasutab kirjeldatud algoritmi. Pange tähele while-tsükli tingimusi. Selle programmi jaoks sobiv C põhifunktsioon on:
{
int n = 8 ;
int A [ ] = { viiskümmend , 60 , 30 , 10 , 80 , 70 , kakskümmend , 40 } ;
sisestamineSorteeri ( A, n ) ;
jaoks ( int i = 0 ; i < n; i++ ) {
printf ( '%i' , A [ i ] ) ;
}
printf ( ' \n ' ) ;
tagasi 0 ;
}
Järeldus
Sisestuse sortimise ajaline keerukus on esitatud järgmiselt:
Peal kaks )
Lugeja võis kuulda halvema aja keerukusest, keskmisest ajalisest keerukusest ja parimal juhul aja keerukusest. Neid sisestuse sortimise aja keerukuse variatsioone käsitletakse meie veebisaidi järgmises artiklis.