Sortointi

Sortointi tarkoittaa joukon alkioiden järjestämistä sääntöjen mukaan, yleisimmin nousevaan tai laskevaan järjestykseen avaimen perusteella. Tavoitteena on helpottaa tietojen hakua, vertailua ja analysointia sekä valmistella data esimerkiksi taulukko- tai hakualgoritmeja varten.

Yleisimpiä sorttausalgoritmeja ovat vertailuun perustuvat tekniikat kuten quicksort, mergesort ja heapsort sekä pienille listoille tarkoitetut insertion-sort ja bubble-sort. Keskimäärin tehokkaimmat yleiskäyttöiset algoritmit ovat O(n log n) ajassa. Quicksort on usein erittäin nopea käytännössä, mutta pahimmillaan sen aikavaativuus on O(n^2) ilman erityisiä parannuksia; mergesort tarjoaa tasaisen O(n log n) ja on vakaata, mutta vaatii lisätilaa; heapsort on in-place ja O(n log n), mutta voi olla käytännössä hieman hitaampi. Erikoistuneet menetelmät kuten counting sort, radix sort ja bucket sort toimivat tehokkaasti, kun avaimet ovat rajoitetun kokoisia tai hyväksytyn jakauman mukaan.

Sortoinnin ominaisuuksiin kuuluu vakaa järjestys (stability) ja in-place-tyyppi (tarvitsetko lisämuistia). Vakaa sorttaus säilyttää saman avaimen esiintymien alkuperäisen järjestyksen; toiset algoritmit eivät sitä takaa. Valinta riippuu datan määrästä, muistivaatimuksista ja siitä, käytetäänkö sorttia toistuvasti vai vain kerran. Lisäksi voidaan määrittää, että sortointi toteutetaan yhdellä avaimella tai useammalla avainarvolla sekä kohdistaa yhdenmukainen nouseva tai laskeva järjestys.

Sovelluksia ovat esimerkiksi tietojen järjestäminen parempaa hakua varten, indeksointi, tilastolliset analyysit sekä käyttöliittymät, joissa lista on helpompi lukea. Suurten datasetien tapauksessa voidaan käyttää external sorting -tekniikoita, joissa osa dataa pysyy ulkoisessa tallennustilassa ja järjestely tehdään useissa vaiheissa.