| << 2.1 Otsimine | Sisukord | 2.3 Graafid >> |
Tunni läbimisel:
- Tean, mis on sorteerimisalgoritm
- Tean, kuidas töötab mullimeetodil sorteerimine
- Tean, kuidas töötab valikumeetodil sorteerimine
- Tean, kuidas töötab kiirmeetodil sorteerimine
- Oskan hinnata sorteerimeetodi ajalist keerukust, kui ma selle tööpõhimõttest aru saan
2.2 Sorteerimine
Eelmises osas nägime, et sorteeritud järjendist on elementide otsimine oluliselt kiirem, kui sorteerimata järjendist. Sorteerimiseks leidub palju erinevaid viise, kuidas näiteks sina kaardipakki sorteeriksid?
Definitsioon: sorteerimisalgoritm - selline algoritm, mis paneb elemendid järjendis kindlasse järjekorda. Selleks järekorrask võib olla näiteks numbriline järjestus või tähestikuline järjestus.
Erinevalt aga kaardipaki sorteerimisest ei saa sorteerimise puhul elemente lihtsalt järjendi keskele pista, kuna arvuti mälus asuvad kõik andmed üksteise kõrval järjestikku. Kuigi Pythonis on olemas insert() meetod, mis võimaldab elemente lisada ka järjendi keskele, siis tegelikult peab ta selle jaoks ruumi tegema, ehk kõik järgnevad elemendid ühe võrra edasi kopeerima. Seda on kujutatud järgmisel joonisel:
NB! Ära kasuta insert() meetodit sorteerimisalgoritmides, see on aeglane!
Kuna järjendi keskele lisamine on aeglane, siis enamik sorteerimisalgoritme hoopis vahetab elemete omavahel. Mis on elementide vahetamise ja keskele lisamise keerukused?
- Elementide vahetamine - {$ O(1) $}
- Elementide lisamine - {$ O(n) $}
Ülesanne 1
Järgnev algoritm sorteerib järjendi kasutades mullimeetodit. Tegemist on ühe lühima sorteerimisalgoritmiga, kuigi see pole eriti kiire.
Vasta järgmistele küsimustele:
- Miks on elementide vahetamiseks vaja kasutada abi muutujat?
- Kas see algoritm sorteerib järjendi kasvavalt või kahanevalt?
- Mida tuleks algoritmis muuta, et sorteerida järjend teistpidi (näiteks kui ta praegu sorteerib kasvavalt, siis panna kahanevalt sorteerima)?
- Mis on selle algoritmili ajaline keerukus?
- Sest ilma lisamuutujat kasutamata kirjutaksime me kõigepealt ühe väärtuse üle ning kui me seda meelde ei jäta, siis me ei tea enam, millega teist väärtust üle kirjutada.
- Kasvavalt.
- Tingimuslauses tuleks suurem märk > asendada väiksem märgiga <.
- {$ O(n^2) $}
Valikumeetod Mullimeetodist kiirem sorteerimismeetod on valikumeetod. Selle sorteerimisalgoritmi tööpõhimõte on lihtne: esimesel iteratsioonil otsime järjendist vähima väärtusega elemendi ning vahetame selle ära esimese elemendiga selles järjendis. Seejärel me esimest elementi rohkem ei vaata, vaid otsime ülejäänud järjendist uuesti vähima väärtusega elemendi, ning vahetame selle ära teise elemendiga selles järjendis. Kordame seda protsessi, kuni alles on jäänud ainult viimane element, seda me enam millegagi ei vaheta. Mis on selle algoritmi ajaline keerukus?
Näide: Sorteerime valikumeetodil järjendit numbritega. Joonisel on hallide kaartidena tähistatud järjendi elemendid ning kaardi all märgitud number tähistab tema asukohta järjendis. Esimesel sammul vaatame kõik järjendi elemendid läbi ning leiame vähima väärtuse.
Vahetame selle elemendi ära kõige esimese elemendiga selles järjendis.
Nüüd on esimene element järjendis sorteeritud, seda enam rohkem ei vaata ning otsime alles jäänud elementidest uuesti vähima elemendi.
Vahetame leitud elemendi järjendis teisel kohal oleva elemendiga (kuna esimene element on eelnevalt juba paika pandud).
Jätkame sama protsessi, vahetades järgmisena elemendid 12 ja 9.
Võib juhtuda, et vähim element on juba õigel kohal. Sellisel juhul võime nö. vahetada selle arvu iseendaga, mille tulemusena midagi ei muutu
Kui oleme kõik elemendid läbi vaadanud, lõpetab algoritm töö. Tegelikult võib viimase sammu isegi vahele jätta, sest kui alles on jäänud ainult üks arv (anud juhul 13) on see juba kindlasti õiges kohas.
Ülesanne 2
Realiseeri iseseisvalt valikumeetodil põhinev sorteerimisalgoritm.
- Kui sa ei tea, millest alustada, kirjuta kõigepealt listist vähima väärtuse leidmise algoritm.
- Vähima väärtuse leidmise algoritmile lisa ümber veel üks tsükkel, mis kordub n-1 korda ja selles tsükklis defineeritud muutuja määrab ära, millise elemendini järjendi alguses on meil elemendid sorteeritud. Sellest elemendist (kaasa arvatud) eespool paiknevaid elemente me rohkem ei võrdle.
Ülesanne 2
Kuigi valikumeetod on mullimeetodist kiirem, ei ole see siiski piisavalt kiire, et sorteerida suuri andmemahtusid. Oluliselt parem sorteerimismeetod on kiirmeetod ning nagu nimigi ütleb on see väga kiire ja on kasutusel paljudes programmeerimiskeeltes peamise sorteerimisalgoritmina.
Kiirmeetodi tööpõhimõte seisneb selles, et esmalt valitakse järjendist üks juhuslik element (näiteks kõige esimene elment) ning seejärel järjestatakse list selliselt, et kõigepealt on seal valitud elemendist väiksemad ja seejärel temast suuremad elemendid. Seejärel korratakse seda algoritmi mõlema poole peal uuesti (kõigi väiksemate elmentide hulgast valitakse jälle üks juhuslik element ning ülejäänud elemendid jagatakse seal sees ringi), kuni tekkinud osadesse on jäänud nii vähe elemente, et nende järjestamine on triviaalne. Kiirmeetodi algoritmi saab näha ja proovida näiteks siin: https://pythonschool.net/data-structures-algorithms/quicksort/
Kiirmeetodil sorteerimise keskmine ajaline keerukus on {$ O(n*log_2n) $}, mis on väga hea. Halvimal juhul on selle keerukuseks aga {$ O(n^2) $}.
- Milline on selle algoritmi jaoks halvim olukord?
- Kuidas saaks seda olukorda ära hoida?
- Halvim olukord tekib siis, kui igal sorteerimise etapil juhtub valitud elemendiks vähim element. Sellisel juhul ei jaga see algoritm ülejäänud elemente kaheks, vaid jääb ise esimeseks elemendiks ning kõik ülejäänud elemendid on temast suuremad ning see kõik kordub järgmistel ettappidel uuesti. Näiteks kui valida juhuslikuks elemendiks alati kõige esimene element, siis tekib selline olukord juhul, kui järjend on alguses juba sorteeritud kujul.
- Kuna halvim olukord tekib statistiliselt väga harva, siis aitab, kui valida see juhuslik element tõepoolest juhuslikult. Keskmise elemendi valimine on samuti üsna tõhus strateegia.
Lisaülesanded
- Kui palju kulutavad ülesannetes kirjeldatud algoritmid lisamälu andmehulga kasvades. Ehk siis, mis on nende algoritmide mälu keerukus?
- Kui kiirmeetod oli halvimal juhul halvema keerukusega, kui {$ O(n*log_2n) $}, siis mestimismeetod on alati ajalise keerukusega {$ O(n*log_2n) $} ka halvimal juhul. Realiseeri interneti abiga see meetod: https://en.wikipedia.org/wiki/Merge_sort.
- Kas on võimalik teha sorteerimismeetod, mis on ka halvimal juhul keerukusega {$ O(n) $}, ehk iga elemendiga tehakse alati sama palju operatsioone, olenemata sellest, kui palju sorteeritavaid elemente kokku on. Kui on võimalik, siis mida me peame nende andmete kohta eelnevalt teadma?
Selles peatükis nägime, et arvuti seab täpsed nõuded sellele, kuidas me andmeid hoidma peame. Järgmises peatükis vaatame, mis on graaf, kuidas kujutada ülesannet graafina ning kuidas hoida graafe arvuti mälus.
Mõisted:
- sorteerimisalgoritm - selline algoritm, mis paneb elemendid järjendis kindlasse järjekorda. Selleks järekorrask võib olla näiteks numbriline järjestus või tähestikuline järjestus.
Viited:
| << 2.1 Otsimine | Sisukord | 2.3 Graafid >> |