Sorteerimisalgoritmid

Sorteerimisalgoritmid on arvutiteaduses meetodid andmestruktuuri elementide järjestamiseks kindla võrdlus- või võtmejärjestuse alusel. Sorteerimine on fundamentaalne operatsioon, mida kasutatakse otsingutes, andmete esituses ja andmetöötluse eeltöötluses.

Levinumad algoritmid hõlmavad lihtsaid võrdluspõhiseid meetodeid nagu mullisorteerimine (bubble sort), valikusorteerimine (selection sort) ja sisestussorteerimine (insertion sort), mis on intuitiivsed, kuid neil on tavaliselt ajakompleksus O(n^2). Tõhusamad O(n log n) lahendused on ühenda­sorteerimine (merge sort), kiirsorteerimine (quicksort) ja kuhjasorteerimine (heapsort). Spetsiifiliste võtmepopiirangute korral kasutatakse arvulisi lineaaraja algoritme nagu lugemissorteerimine (counting sort), positsioonisorteerimine (radix sort) ja kasti­sorteerimine (bucket sort).

Olulised omadused on aja- ja mälukompleksus, stabiilsus (ühetaoliste elementide suhtelise järjekorra säilimine), ning kas algoritm töötab kohapeal (in-place) või vajab lisamälu. Näiteks merge sort on sageli stabiilne, kuid nõuab lisamälu; quicksort on tavaliselt kohapeal, ent mitte stabiilne.

Praktilised valikud sõltuvad andmete suurusest, mälupiirangutest ja nõutavast stabiilsusest. Välistes (välismälus) tingimustes kasutatakse sageli mitmeastmelist ühendamist (external merge sort). Paralleelsed ja jaotatud variandid (nt parallel quicksort, sample sort) optimeerivad kiirust mitme tuuma või sõlme puhul.

Sorteerimisalgoritmid on intensiivselt uuritud teoreetiliselt ja rakenduslikult, ning enamik programmeerimiskeelte standardraamatukogud pakub optimiseeritud sorteermisfunktsioone.