sorteerimisalgoritmides

Sorteerimisalgoritm on algoritm, mille eesmärk on järjestada elemendid kindla võrdlusreegli alusel kasvavas või kahanevas järjekorras. Erinevad algoritmid lahendavad sama ülesande erinevate omadustega ning sobiv valik sõltub andmete suurusest, tüübist ja rakenduse nõudmistest.

Sortimist saab jagada peamiselt võrdlus- ja mittevõrdlushordusteks. Võrdluspõhised sorteerimised kasutavad elementide võrdlemist, et määrata nende järjekord. Mittevõrdlushordused kasutavad eeldusi võtmete väärtuste kohta või rakendavad digit- või vahemikupõhiseid meetodeid, mis võivad anda ajalises ja ruumimõttes erilise efektiivsuse. Näiteks Counting sort, Radix sort ja Bucket sort on efektiivsed kindlate piirangutega võtmetele.

Levinud võrdluspõhised sorteerimised jagunevad omakorda mitmeks põhiprotessiks: Insertion sort ja Bubble sort on lihtsad, kuid tavaliselt aeglased O(n^2) sorteerimised; Selection sort on in-place, kuid mitte-stabiilne ja samuti O(n^2). QuickSort on tavaliselt kiire, keskmiselt O(n log n), kuid halvimad juhtumid võivad olla O(n^2); see on tavaliselt in-place ja mitte-stabiilne. MergeSort töötab alati O(n log n), on stabiilne, kuid tavaliselt vajab lisaruumi (väliskasutuse variant võib olla järgne). HeapSort on O(n log n), in-place, kuid mitte-stabiilne.

Mittevõrdlushordustel on näiteks Counting sort ja Radix sort, mis võivad pakkuda lineaarset aega teatud tingimustel; need on tavaliselt stabilsed ja vajavad lisamälu. Valik sõltub võtmete suurusest, soovitud stabiilsusest ja mälu piirangutest ning andmete suurusest. Eksamil või tarkvaras kasutatakse sageli kombineeritud lähenusi, et saavutada parem jõudlus.