Sortimisalgoritm
Sortimisalgoritm on matemaatikas ja informaatikas algoritm loendi elementide paigutamiseks kindlasse järjekorda.
Levinuimad järjestusviisid on numbriline ja tähestikuline järjekord. Sortimine on vajalik, et optimeerida teiste algoritmide (näiteks otsimisalgoritm) kasutust, mis vajavad sisenditena sorditud loendeid. Sortimine on tihti kasulik andmete normaliseerimiseks ja inimesele loetava väljundi tekitamiseks. Formaalselt peab väljund täitma kahte tingimust:
- olema mittekahanevas järjestuses (iga element on mitteväiksem talle eelnenud elemendist)
- olema sisendi permutatsioon.
Alates arvutusteaduste tekkest on sortimine köitnud paljude teadlaste tähelepanu. Põhjuseks on ülesande tähtsus, võimalike algoritmide suur hulk ja nende väga erinev keerukus, vaatamata probleemi lihtsale olemusele. Näiteks mullsortimist analüüsiti juba 1956. aastal.
Tänapäeva arvutite töökiiruse juures ei ole oluline, missuguse algoritmiga väikeseid loendeid sortida. Seevastu suurte loendite (miljonid ja miljardid elemendid) korral on kasutatav sortimise algoritm tähtis.
Ühest vastust küsimusele, missugune sortimisalgoritm on parim, ei saa anda. See sõltub kasutavatest andmetest. Näiteks mullsortimine on üldjuhul ja halvimal juhul palju aeglasem kui mestimissortimine, kuid peaaegu sorditud jadade sortimisel sellest märgatavalt kiirem. Valiksortimine on aeglasem kui Shelli sortimine nii parimal, halvimal kui üldjuhul – ent seda ainult suurte andmekogumite korral, väikeste loendite sortimisel on ta sellest märksa kiirem.
Kuigi mõned peavad seda lahendatud probleemiks[viide?], luuakse siiani uusi ning kasulikke sortimisalgoritme[viide?]. Sortimisalgoritmid on valdavad informaatika sissejuhatavates kursustes, kuna algoritmide küllus probleemi lahendamiseks tutvustab erinevaid algoritmikeskseid mõisteid, nagu jaga ja valitse algoritmid, andmestruktuurid, juhuslikud algoritmid, parim, halvim ja üldjuhtum ning muud.
Stabiilsus muuda
Kui loendis leidub võrdseid elemente, saab väljundil olla mitu võimalikku järjestust. Näiteks sortides tooteid hinna järgi, saab võrdse hinnaga toodetel olla omavahel erinev järjestus. Sortimisalgoritmi nimetatakse stabiilseks, kui väljundis on võrdsetel elementidel alati sama järjestus kui sisendis.
| Hind | Nimetus |
|---|---|
| 10 € | Kala |
| 4 € | Juust (1) |
| 1 € | Banaan |
| 4 € | Salat (2) |
| Hind | Nimetus |
|---|---|
| 1 € | Banaan |
| 4 € | Juust (1) |
| 4 € | Salat (2) |
| 10 € | Kala |