Trys algoritmai pseudokodu

Trys algoritmai. Kodo čia nerasi — rasi tai, ko reikia jam parašyti.

Burbuliukų rikiavimas

Eik per masyvą ir sukeisk kiekvieną gretimą porą, kuri ne tvarkoje. Po vieno perėjimo didžiausias elementas jau gale. Kartok, kol perėjimas nepadaro nė vieno sukeitimo.

kartok:
    swapped ← ne
    kiekvienam i nuo 0 iki end-1:
        cmp.Hit()
        jei items[i].Title > items[i+1].Title:
            sukeisk items[i] ir items[i+1]
            swap.Hit()
            swapped ← taip
    end ← end - 1
    jei ne swapped: baik

swapped vėliavėlė nėra puošmena: be jos burbuliukų rikiavimas ir surikiuotam masyvui atliktų visus n perėjimų. Su ja — vieną.

Griežtai >, niekada >=. Sukeitęs lygius elementus sugriautum stabilumą.

Išrinkimo rikiavimas

Surask mažiausią likusį elementą ir sukeisk jį į vietą. Kartok kiekvienai pozicijai.

kiekvienam i nuo 0 iki n-2:
    min ← i
    kiekvienam j nuo i+1 iki n-1:
        cmp.Hit()
        jei items[j].Title < items[min].Title:
            min ← j
    jei min ≠ i:
        sukeisk items[i] ir items[min]
        swap.Hit()

Atkreipk dėmesį: vidinis ciklas visada nueina iki galo. Nesvarbu, ar masyvas jau surikiuotas — mažiausio elemento kitaip nerasi. Todėl išrinkimo rikiavimas neturi geriausio atvejo, ir testas to reikalauja tiesiogiai.

Mainais gauni vieną dalyką: ne daugiau kaip n−1 sukeitimų. Iš trijų algoritmų tai mažiausiai judinamų duomenų.

Įterpimo rikiavimas

Imk kiekvieną elementą iš eilės ir stumk jį kairėn, kol atsiduria savo vietoje tarp jau sutvarkytų.

kiekvienam i nuo 1 iki n-1:
    cur ← items[i]
    j ← i - 1
    kol j >= 0:
        cmp.Hit()
        jei items[j].Title <= cur.Title: baik ciklą
        items[j+1] ← items[j]
        swap.Hit()
        j ← j - 1
    items[j+1] ← cur

Svarbiausia eilutė — jei items[j].Title <= cur.Title: baik ciklą.

Ji nutraukia stūmimą iškart, kai vieta rasta. Jei masyvas jau surikiuotas, kiekvienam elementui užtenka vieno palyginimo, ir visas rikiavimas kainuoja n−1 palyginimų ir nulį sukeitimų.

Šita eilutė — visa pamokos esmė. Įsidėmėk ją; 6 žingsnyje pamatysi, kiek ji verta.

<=, ne <. Su < lygūs elementai vis tiek keistųsi vietomis ir prarastum stabilumą.

Stabilumas

Rikiavimas stabilus, jei vienodi raktai išlaiko pradinę tarpusavio tvarką.

Burbuliukų ir įterpimo rikiavimai stabilūs, nes keičia tik gretimus elementus: du lygūs elementai vienas per kitą peršokti negali.

Išrinkimo rikiavimas — ne. Jis meta elementą per savavališką atstumą, ir tas šuolis gali permesti vieną lygų elementą per kitą. Testas šito reikalauja: jei tavo išrinkimo rikiavimas staiga taps stabilus, testas praneš — ir tada verta pasižiūrėti, kiek sukeitimų tai kainavo.