sortaminen

Sortaminen tarkoittaa alkioiden järjestämistä etukäteen määritellyn kriteerin mukaan, tavallisesti nousevaan tai laskevaan järjestykseen. Kriteeri muodostuu avaimesta, jonka mukaan alkioita vertaillaan. Sortointi on keskeinen operaatio tiedon käsittelyssä ja sitä käytetään esimerkiksi hakujen tehostamiseen, luetteloinnin selkeyttämiseen sekä erojen tai ryhmien tunnistamiseen.

Tietojenkäsittelytieteessä sortaminen on perusoperaatio, jonka tavoitteena on tehdä tiedosta helpommin haettavaa ja analysoitavissa olevaa. Sortointi voidaan toteuttaa vertailemalla alkioita tai käyttämällä ei-vertailuperusteisia menetelmiä, jolloin aikavaatimukset voivat poiketa riippuen avaimien ominaisuuksista.

Yleisimmät vertailuperusteiset algoritmit ovat insertion sort, selection sort ja bubble sort, jotka ovat yksinkertaisia mutta usein tehotonta suurille dataseteille. O(n log n) -aikavaatimuksilla toimivat mergesort ja heapsort; mergesort on tavallisesti vakaa ja soveltuu suurille jaettavalle datalle, kun taas heapsort on ei-stabiili mutta tilankäytöltään tehokas. Quicksort on keskimäärin erittäin nopea (noin O(n log n)) mutta huonoin tapauksin voi olla O(n^2). Ei-vertailuperusteiset menetelmät kuten radix sort, counting sort ja bucket sort voivat tarjota lineaarisen aikavaatimuksen joillekin avaimityypeille.

Sortin käytännön huomioita ovat vakaus, tilankäyttö sekä se, miten järjestys määritellään kielellisesti tai kulttuurisesti (collation). Kansainvälisessä ympäristössä merkkijonojen sortointi voi vaatia Unicode-normalisointia ja locale-asetuksia.

Sovelluksia ovat tietokannat, käyttöliittymät, raportointi sekä suurten datasetien ulkoinen sortointi. Monimutkaisissa tapauksissa käytetään rinnakkaisia tai hajautettuja toteutuksia sekä moniulotteista, moni-kriteeristä sorttia.