Sortimisalgoritm

Allikas: Vikipeedia

Sortimisalgoritm on matemaatikas ja informaatikas algoritm, mis paneb loendi elemendid 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.

Vaata ka[muuda | redigeeri lähteteksti]