Turinys[Slėpti][Rodyti]
Kompiuterių mokslas yra skirtas suprasti algoritmų ir duomenų struktūrų sudėtingumą.
Turite elementų, kuriuos reikia rūšiuoti, sąrašą, bet neturite laiko ar išteklių naudoti sudėtingesnį rūšiavimo algoritmą.
Įterpimo rūšiavimas yra vienas iš paprasčiausių rūšiavimo algoritmų, tačiau dideliems sąrašams jis gali būti lėtas.
Lengvas įgyvendinimas ir supratimas padarė šį metodą mėgstamiausiu tarp programuotojų. Puikiai tinka mažiems sąrašams arba kai reikia greito sprendimo.
Šiame tinklaraščio įraše apžvelgsime įterpimo rūšiavimo sudėtingumą. Šis algoritmas naudojamas masyvams rūšiuoti, o jo vykdymo laikas yra O(n2). Tai reiškia, kad laiko sudėtingumas didėja didėjant masyvo dydžiui.
Tačiau šis algoritmas dažnai gali būti greitesnis nei kiti rūšiavimo algoritmai, pvz., greitasis rūšiavimas.
Pažiūrėkime atidžiau, kaip veikia įterpimo rūšiavimas!
Kas yra įterpimo rūšiavimo algoritmas?
Po vieną elementą, įterpimo rūšiavimas sukuria rūšiuojamą masyvą, kuris dažnai vadinamas sąrašu.
Pavyzdžiui, rūšiavimas taikomas sudėtingose kompiuterinėse programose, tokiose kaip kompiliatoriai, kur žetonų tvarka yra svarbi programos interpretavimui.
Kaip veikia įterpimo rūšiavimas?
Kai masyvo rūšiavimui naudojame įterpimo rūšiavimą, algoritmas pradedamas ieškant mažiausio sąrašo elemento ir įterpiant jį į tinkamą vietą.
Tada jis suranda kitą mažiausią elementą ir įdeda jį į reikiamą padėtį ir pan.
Algoritmas veikia peržiūrint sąrašą, lyginant kiekvieną elementą su esančiu prieš jį.
Jei elementai yra neteisinga tvarka, algoritmas juos pakeičia. Tada patikrinama, ar sąrašas surūšiuotas, o jei taip, algoritmas baigiasi.
Praktiškai įterpimo rūšiavimas dažnai įgyvendinamas naudojant kelias kodo eilutes, todėl tai yra populiarus pasirinkimas rūšiuojant mažus masyvus. Tačiau naudojant šį algoritmą reikia atsižvelgti į laiko sudėtingumą.
Pavyzdys:
Štai pavyzdys, kaip veikia įterpimo rūšiavimas. Mes naudosime šį masyvą:
1, 2, 3, 4, 5, 6
Algoritmas pradedamas ieškant mažiausio sąrašo elemento, kuris yra 1. Tada įterpia jį į teisingą, pirmąją, poziciją. Tada jis suranda kitą mažiausią elementą, kuris yra 2. Jis įterpia jį į teisingą padėtį, kuri yra antroji.
Tada jis suranda kitą mažiausią elementą, kuris yra 3. Jis įterpia jį į teisingą padėtį, kuri yra trečia.
Tada jis suranda kitą mažiausią elementą, kuris yra 4. Jis įterpia jį į teisingą padėtį, kuri yra ketvirta padėtis ir pan. Dabar sąrašas surūšiuotas!
Iš pavyzdžio matome, kad algoritmui reikia šešių palyginimų ir apsikeitimų, kad surūšiuotų sąrašą. Taip yra todėl, kad reikia n2 palyginimai ir apsikeitimai n elementų sąrašui surūšiuoti. Šiuo atveju n = 6.
Kaip pagerinti įterpimo rūšiavimo laiko sudėtingumą?
Nors įterpimo rūšiavimo vykdymo laikas yra O(n2), jį galima patobulinti naudojant geresnį rūšiavimo algoritmą, pvz., greitąjį rūšiavimą.
Quicksort turi O(n log n) vykdymo laiką, kuris yra daug greitesnis nei O(n2).
Tačiau kai kuriais atvejais įterpimo rūšiavimas gali būti greitesnis nei greitasis rūšiavimas.
Pavyzdžiui, jei sąrašas jau tvarkingas, įterpimo rūšiavimas užtruks mažiau laiko nei greitasis rūšiavimas.
Praktiškai įterpimo rūšiavimas dažnai įgyvendinamas naudojant kelias kodo eilutes, todėl tai yra populiarus pasirinkimas rūšiuojant mažus masyvus.
Tačiau naudojant šį algoritmą reikia atsižvelgti į laiko sudėtingumą.
Laiko sudėtingumas
Blogiausio atvejo sudėtingumas O (n2):
Laiko sudėtingumas didėja didėjant masyvo dydžiui. Tam reikia n2 palyginimai ir apsikeitimai n elementų sąrašui surūšiuoti.
Pavyzdžiui, jei turime 1000 dydžio masyvą, algoritmas imsis 1,000,000 XNUMX XNUMX palyginimų ir apsikeitimų, kad surūšiuotų masyvą.
Geriausio atvejo sudėtingumas O(n):
Laiko sudėtingumas yra toks pat kaip įvesties masyvo dydis. aš
t reikia n palyginimų ir apsikeitimų, kad būtų surūšiuotas n elementų sąrašas. Pavyzdžiui, apsvarstykite 5 dydžio masyvą. Norėdami surūšiuoti masyvą, algoritmas atliks penkis palyginimus ir apsikeitimus.
Vidutinis atvejo sudėtingumas O(n2):
Laiko sudėtingumas šiuo atveju yra tarp blogiausio ir geriausio atvejo sudėtingumo.
Tam reikia n2 palyginimai ir apsikeitimai n elementų sąrašui surūšiuoti.
Taigi, įterpimo rūšiavimas yra stabilus rūšiavimo algoritmas.
Kodėl įterpimo rūšiavimas yra stabilus?
Įterpimo rūšiavimas yra stabilus, nes išlaiko vienodų elementų tvarką įvesties masyve.
Tai svarbu daugeliui programų, pvz., duomenų gavimui ar finansinei analizei. Pavyzdžiui, jei turime du skaičių sąrašus ir norime juos palyginti, turime užtikrinti, kad elementų tvarka būtų išsaugota.
Jei sąrašai nesurūšiuoti, mes jų tiksliai nelyginsime.
Palikti atsakymą