Harkitse seuraavia lukuja:
50 60 30 10 80 70 20 40
Jos tämä luettelo on järjestetty nousevaan järjestykseen, se olisi:
10 20 30 40 50 60 70 80
Jos se on lajiteltu laskevaan järjestykseen, se olisi:
80 70 60 50 40 30 20 10
Lisäyslajittelu on lajittelualgoritmi, jota käytetään lajittelemaan luettelo nousevaan tai laskevaan järjestykseen. Tämä artikkeli käsittelee vain lajittelua nousevaan järjestykseen. Lajittelu laskevaan järjestykseen noudattaa tässä asiakirjassa annettua logiikkaa. Tämän artikkelin tarkoituksena on selittää lisäyslajittelu. Ohjelmointi tehdään seuraavassa esimerkissä C:ssä. Lisäyslajittelu selitetään tässä yhden taulukon avulla.
Lisäyslajittelun algoritmi
Lajittelematon luettelo annetaan. Tarkoituksena on lajitella lista nousevaan järjestykseen käyttäen samaa listaa. Lajittelemattoman taulukon lajittelemisen samalla taulukolla sanotaan olevan paikan päällä lajittelua. Tässä käytetään nollapohjaista indeksointia. Vaiheet ovat seuraavat:
-
- Lista skannataan alusta alkaen.
- Skannauksen aikana mikä tahansa numero, joka on pienempi kuin edeltäjänsä, vaihdetaan edeltäjäänsä.
- Tämä vaihto jatkuu listaa pitkin, kunnes vaihtaminen ei ole enää mahdollista.
- Kun skannaus päättyy, lajittelu on valmis.
Lisäyslajittelukuva
Ajan monimutkaisuutta käsiteltäessä yleensä otetaan huomioon pahin tapaus. Edellisen listan huonoin järjestely on:
80 70 60 50 40 30 20 10
Siinä on kahdeksan elementtiä, joiden indeksit ovat nollasta 7:ään.
Indeksillä nolla skannaus menee 80:een. Tämä on yksi liike. Tämä yksi liike on operaatio. Tähän mennessä on tehty yhteensä yksi operaatio (yksi liike, ei vertailua eikä vaihtoa). Tulos on:
| 80 70 60 50 40 30 20 10
Indeksissä yksi on liike 70:een. 70:tä verrataan 80:een. 70 ja 80 vaihdetaan. Yksi liike on yksi operaatio. Yksi vertailu on myös yksi operaatio. Yksi vaihto on myös yksi operaatio. Tämä osio sisältää kolme toimintoa. Leikkauksia on tähän mennessä yhteensä neljä (1 + 3 = 4). Tulos on seuraava:
70 | 80 60 50 40 30 20 10
Indeksissä kaksi tapahtuu liike 60:een. 60:tä verrataan 80:een, sitten 60 ja 80 vaihdetaan. 60 verrataan 70:een, sitten 60 ja 70 vaihdetaan. Yksi liike on yksi operaatio. Kaksi vertailua on kaksi operaatiota. Kaksi vaihtoa on kaksi operaatiota. Tämä osio sisältää viisi toimintoa. Toistaiseksi operaatioita on yhteensä yhdeksän (4 + 5 = 9). Tulos on seuraava:
60 70 | 80 50 40 30 20 10
Indeksillä kolme tapahtuu liike 50:een. 50:tä verrataan 80:een, sitten 50 ja 80 vaihdetaan. 50 verrataan 70:een, sitten 50 ja 70 vaihdetaan. 50 verrataan 60:een, sitten 50 ja 60 vaihdetaan. Yksi liike on yksi operaatio. Kolme vertailua on kolme toimenpidettä. Kolme vaihtoa on kolme operaatiota. Tämä osio sisältää seitsemän toimintoa. Leikkauksia on tähän mennessä yhteensä kuusitoista (9 + 7 = 16). Tulos on seuraava:
50 60 70 | 80 40 30 20 10
Indeksillä neljä tapahtuu liike 40:een. 40:tä verrataan 80:een, sitten 40 ja 80 vaihdetaan. 40 verrataan 70:een, sitten 40 ja 70 vaihdetaan. 40 verrataan 60:een, sitten 40 ja 60 vaihdetaan. 40 verrataan 50:een, sitten 40 ja 50 vaihdetaan. Yksi liike on yksi operaatio. Neljä vertailua on neljä operaatiota. Neljä vaihtoa on neljä operaatiota. Tämä osio sisältää yhdeksän toimintoa. Leikkauksia on tähän mennessä yhteensä kaksikymmentäviisi (16 + 9 = 25). Tulos on seuraava:
40 50 60 70 80 | 30 20 10
Indeksillä 5 tapahtuu liike 30:een. 30:tä verrataan 80:een, sitten 30 ja 80 vaihdetaan. 30 verrataan 70:een, sitten 30 ja 70 vaihdetaan. 30 verrataan 60:een, sitten 30 ja 60 vaihdetaan. 30 verrataan 50:een, sitten 30 ja 50 vaihdetaan. 30 verrataan 40:een, sitten 30 ja 40 vaihdetaan. Yksi liike on yksi operaatio. Viisi vertailua on viisi operaatiota. Viisi vaihtoa on viisi operaatiota. Tämä osio sisältää yksitoista toimintoa. Leikkauksia on tähän mennessä tehty yhteensä kolmekymmentäkuusi (25 + 11 = 36). Tulos on seuraava:
30 40 50 60 70 80 | 20 10
Indeksissä kuusi tapahtuu liike 20:een. 20 verrataan 80:een, sitten 20 ja 80 vaihdetaan. 20 verrataan 70:een, sitten 20 ja 70 vaihdetaan. 20 verrataan 60:een, sitten 20 ja 60 vaihdetaan. 20 verrataan 50:een, sitten 20 ja 50 vaihdetaan. 20 verrataan 40:een, sitten 20 ja 40 vaihdetaan. 20 verrataan 30:een, sitten 20 ja 30 vaihdetaan. Yksi liike on yksi operaatio. Kuusi vertailua on kuusi operaatiota. Kuusi vaihtoa on kuusi operaatiota. Tämä osio sisältää kolmetoista toimintoa. Leikkauksia on tähän mennessä yhteensä 49 (36 + 13 = 49). Tulos on seuraava:
20 30 40 50 60 70 80 | 10
Indeksillä seitsemän tapahtuu liike 10:een. 10:tä verrataan 80:een, sitten 10 ja 80 vaihdetaan. 10 verrataan 70:een, sitten 10 ja 70 vaihdetaan. 10 verrataan 60:een, sitten 10 ja 60 vaihdetaan. 10 verrataan 50:een, sitten 10 ja 50 vaihdetaan. 10 verrataan 30:een, sitten 10 ja 40 vaihdetaan. 10 verrataan 30:een, sitten 10 ja 30 vaihdetaan. 10 verrataan 20:een, sitten 10 ja 20 vaihdetaan. Yksi liike on yksi operaatio. Seitsemän vertailua on seitsemän operaatiota. Seitsemän vaihtoa on seitsemän operaatiota. Tämä osio sisältää viisitoista toimintoa. Leikkauksia on tähän mennessä yhteensä kuusikymmentäneljä (49 + 15 = 64). Tulos on seuraava:
10 20 30 40 50 60 70 80 10 |
Työ on tehty! Mukana oli 64 operaatiota.
64 = 8 x 8 = 8 kaksi
Aika monimutkaisuus lisäyslajittelussa
Jos Insertion Sort -toiminnolla lajitettavia elementtejä on n, mahdollisten operaatioiden enimmäismäärä on n2, kuten aiemmin osoitettiin. Lisäyksen lajitteluajan monimutkaisuus on:
Päällä kaksi )
Tämä käyttää Big-O-merkintää. Big-O-merkintä alkaa O:lla isoilla kirjaimilla, jota seuraa sulkumerkit. Suluissa on operaatioiden enimmäismäärän lauseke.
Koodaus C-kielellä
Aivan skannauksen alussa ensimmäinen elementti ei voi muuttaa sijaintiaan. Ohjelma on pohjimmiltaan seuraava:
#includetyhjä lisäysLajittele ( int A [ ] , int N ) {
varten ( int i = 0 ; i < N; i++ ) {
int j = i;
sillä aikaa ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
sisälämpötila = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = lämpötila; // vaihtaa
j--;
}
}
}
InsertionSort()-funktion määritelmä käyttää kuvattua algoritmia. Huomaa while-silmukan ehdot. Sopiva C-päätoiminto tälle ohjelmalle on:
{
int n = 8 ;
int A [ ] = { viisikymmentä , 60 , 30 , 10 , 80 , 70 , kaksikymmentä , 40 } ;
lisäysLajittele ( A, n ) ;
varten ( int i = 0 ; i < n; i++ ) {
printf ( '%i' , A [ i ] ) ;
}
printf ( ' \n ' ) ;
palata 0 ;
}
Johtopäätös
Lisäyslajittelun aika monimutkaisuus on annettu seuraavasti:
Päällä kaksi )
Lukija on saattanut kuulla pahemman tapauksen ajan monimutkaisuudesta, keskimääräisen tapauksen aikamonimutkaisuudesta ja parhaan tapauksen ajan monimutkaisuudesta. Näitä lisäyslajitteluajan monimutkaisuuden muunnelmia käsitellään verkkosivustomme seuraavassa artikkelissa.