Apsvarstykite šiuos skaičius:
50 60 30 10 80 70 20 40
Jei šis sąrašas surūšiuotas didėjančia tvarka, jis būtų toks:
10 20 30 40 50 60 70 80
Jei jis surūšiuotas mažėjančia tvarka, tai būtų:
80 70 60 50 40 30 20 10
Įterpimo rūšiavimas yra rūšiavimo algoritmas, naudojamas sąrašui rūšiuoti didėjimo arba mažėjimo tvarka. Šiame straipsnyje aptariamas tik rūšiavimas didėjančia tvarka. Rūšiavimas mažėjančia tvarka vykdomas pagal šiame dokumente pateiktą logiką. Šio straipsnio tikslas – paaiškinti įterpimo rūšiavimą. Programavimas atliekamas šiame pavyzdyje C. Įterpimo rūšiavimas čia paaiškinamas naudojant vieną masyvą.
Įterpimo rūšiavimo algoritmas
Pateikiamas nerūšiuotas sąrašas. Tikslas yra surūšiuoti sąrašą didėjančia tvarka naudojant tą patį sąrašą. Sakoma, kad nerūšiuoto masyvo rūšiavimas naudojant tą patį masyvą yra rūšiavimas vietoje. Čia naudojamas nulinis indeksavimas. Veiksmai yra tokie:
-
- Sąrašas nuskaitomas nuo pat pradžių.
- Kol vyksta nuskaitymas, bet koks skaičius, mažesnis nei jo pirmtakas, pakeičiamas pirmtaku.
- Šis keitimas tęsiamas sąraše, kol pakeisti nebeįmanoma.
- Kai nuskaitymas pasiekia pabaigą, rūšiavimas baigtas.
Įterpimo rūšiavimo iliustracija
Kalbant apie laiko sudėtingumą, paprastai atsižvelgiama į blogiausią atvejį. Blogiausias ankstesnio sąrašo išdėstymas yra toks:
80 70 60 50 40 30 20 10
Yra aštuoni elementai su indeksais nuo nulio iki 7.
Esant nuliui, nuskaitymas pasiekia 80. Tai vienas judesys. Šis vienas judesys yra operacija. Iš viso kol kas atlikta viena operacija (vienas judesys, jokio palyginimo ir jokio apsikeitimo). Rezultatas yra:
| 80 70 60 50 40 30 20 10
Pirmajame indekse yra pokytis iki 70. 70 lyginamas su 80. 70 ir 80 yra sukeisti. Vienas judesys yra viena operacija. Vienas palyginimas yra ir viena operacija. Vienas apsikeitimas taip pat yra viena operacija. Šiame skyriuje pateikiamos trys operacijos. Iš viso kol kas atliktos keturios operacijos (1 + 3 = 4). Rezultatas yra toks:
70 | 80 60 50 40 30 20 10
Antrame indekse yra poslinkis iki 60. 60 lyginamas su 80, tada 60 ir 80 sukeičiami. 60 lyginamas su 70, tada 60 ir 70 sukeičiami. Vienas judesys yra viena operacija. Du palyginimai yra dvi operacijos. Du apsikeitimai yra dvi operacijos. Šiame skyriuje pateikiamos penkios operacijos. Iš viso kol kas atliktos devynios operacijos (4 + 5 = 9). Rezultatas yra toks:
60 70 | 80 50 40 30 20 10
Trečiame indekse pasislenka iki 50. 50 lyginamas su 80, tada sukeičiami 50 ir 80. 50 lyginamas su 70, tada 50 ir 70 sukeičiami. 50 lyginamas su 60, tada 50 ir 60 sukeičiami. Vienas judesys yra viena operacija. Trys palyginimai yra trys operacijos. Trys apsikeitimai yra trys operacijos. Šiame skyriuje pateikiamos septynios operacijos. Iki šiol iš viso atlikta šešiolika operacijų (9 + 7 = 16). Rezultatas yra toks:
50 60 70 | 80 40 30 20 10
Ketvirtajame indekse pasislenka iki 40. 40 lyginamas su 80, tada sukeičiami 40 ir 80. 40 lyginamas su 70, tada 40 ir 70 sukeičiami. 40 lyginamas su 60, tada 40 ir 60 sukeičiami. 40 lyginamas su 50, tada 40 ir 50 sukeičiami. Vienas judesys yra viena operacija. Keturi palyginimai yra keturios operacijos. Keturi apsikeitimai yra keturios operacijos. Šiame skyriuje pateikiamos devynios operacijos. Iki šiol iš viso atliktos dvidešimt penkios operacijos (16 + 9 = 25). Rezultatas yra toks:
40 50 60 70 80 | 30 20 10
Ties penktuoju indeksu pasislenka iki 30. 30 lyginamas su 80, tada sukeičiami 30 ir 80. 30 lyginamas su 70, tada 30 ir 70 sukeičiami. 30 lyginamas su 60, tada 30 ir 60 sukeičiami. 30 lyginamas su 50, tada 30 ir 50 sukeičiami. 30 lyginamas su 40, tada 30 ir 40 sukeičiami. Vienas judesys yra viena operacija. Penki palyginimai yra penkios operacijos. Penki apsikeitimo sandoriai yra penkios operacijos. Šiame skyriuje pateikiama vienuolika operacijų. Iki šiol iš viso atlikta trisdešimt šešios operacijos (25 + 11 = 36). Rezultatas yra toks:
30 40 50 60 70 80 | 20 10
Šeštajame indekse pasislenka iki 20. 20 lyginamas su 80, tada 20 ir 80 sukeičiami. 20 lyginamas su 70, tada 20 ir 70 sukeičiami. 20 lyginamas su 60, tada 20 ir 60 sukeičiami. 20 lyginamas su 50, tada 20 ir 50 sukeičiami. 20 lyginamas su 40, tada 20 ir 40 sukeičiami. 20 lyginamas su 30, tada 20 ir 30 sukeičiami. Vienas judesys yra viena operacija. Šeši palyginimai yra šešios operacijos. Šeši apsikeitimo sandoriai yra šešios operacijos. Šiame skyriuje pateikiama trylika operacijų. Iki šiol iš viso atliktos keturiasdešimt devynios operacijos (36 + 13 = 49). Rezultatas yra toks:
20 30 40 50 60 70 80 | 10
Esant septintajam indeksui, yra poslinkis į 10. 10 lyginamas su 80, tada 10 ir 80 sukeičiami. 10 lyginamas su 70, tada 10 ir 70 sukeičiami. 10 lyginamas su 60, tada 10 ir 60 sukeičiami. 10 lyginamas su 50, tada 10 ir 50 sukeičiami. 10 lyginamas su 30, tada 10 ir 40 sukeičiami. 10 lyginamas su 30, tada 10 ir 30 sukeičiami. 10 lyginamas su 20, tada 10 ir 20 sukeičiami. Vienas judesys yra viena operacija. Septyni palyginimai yra septynios operacijos. Septyni apsikeitimo sandoriai yra septynios operacijos. Šiame skyriuje pateikiama penkiolika operacijų. Iki šiol iš viso atliktos šešiasdešimt keturios operacijos (49 + 15 = 64). Rezultatas yra toks:
10 20 30 40 50 60 70 80 10 |
Darbas atliktas! Buvo atliktos 64 operacijos.
64 = 8 x 8 = 8 du
Įterpimo rūšiavimo laiko sudėtingumas
Jei yra n elementų, kuriuos reikia rūšiuoti naudojant Insertion Sort, didžiausias galimų operacijų skaičius būtų n2, kaip parodyta anksčiau. Įterpimo rūšiavimo laiko sudėtingumas yra toks:
O (n du )
Tam naudojamas Big-O žymėjimas. „Big-O“ žymėjimas prasideda didžiosiomis raidėmis O, po kurių rašomi skliausteliai. Skliausteliuose yra didžiausio galimo operacijų skaičiaus išraiška.
Kodavimas C
Pačioje nuskaitymo pradžioje pirmasis elementas negali pakeisti savo padėties. Programa iš esmės yra tokia:
#includetuščias įterpimas Rūšiuoti ( tarp A [ ] , tarp N ) {
dėl ( tarpt i = 0 ; i < N; i++ ) {
int j = i;
kol ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
vidinė temperatūra = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temp; // apsikeisti
j--;
}
}
}
Funkcijos insertionSort() apibrėžimas naudoja aprašytą algoritmą. Atkreipkite dėmesį į while ciklo sąlygas. Tinkama pagrindinė šios programos C funkcija yra:
{
int n = 8 ;
tarp A [ ] = { penkiasdešimt , 60 , 30 , 10 , 80 , 70 , dvidešimt , 40 } ;
įterpimas Rūšiuoti ( A, n ) ;
dėl ( tarpt i = 0 ; i < n; i++ ) {
printf ( '%i' , A [ i ] ) ;
}
printf ( “ \n “ ) ;
grąžinti 0 ;
}
Išvada
Įterpimo rūšiavimo laiko sudėtingumas pateikiamas taip:
O (n du )
Skaitytojas galėjo girdėti apie blogesnio atvejo laiko sudėtingumą, vidutinį laiko sudėtingumą ir geriausio atvejo laiko sudėtingumą. Šie įterpimo rūšiavimo laiko sudėtingumo variantai aptariami kitame mūsų svetainės straipsnyje.