Järjestelyalgoritmit

Järjestelyalgoritmit ovat algoritmeja, joiden tehtävänä on asettaa joukko alkioita nousevaan tai laskevaan järjestykseen tietyn avainten perusteella. Niitä käytetään laajalti ohjelmoinnissa ja tietojenkäsittelyssä erilaisten sovellusten, kuten hakemisen ja esittämisen, tukena.

Algoritmit jaotellaan yleisesti vertailupohjaisiin ja ei-vertailupohjaisiin. Vertailupohjaiset algoritmit vertaavat alkioita toisiinsa ja määrittävät niiden järjestyksen: tunnettuja esimerkkejä ovat quicksort, mergesort ja heapsort sekä perinteiset insertion- ja bubble-sort. Ei-vertailupohjaiset menetelmät, kuten counting sort, radix sort ja bucket sort, voivat saavuttaa lineaarisen ajan tietyin edellytyksin, kun avaimien arvot ovat rajoitettuja tai jaettavissa.

Aikavaativuudet vaihtelevat riippuen algoritmista. Vertailupohjaisille järjestelyille yleinen keskimääräinen aika on noin O(n log n). Pahimmassa tapauksessa quicksort voi olla O(n^2), mergesort ja heapsort ovat yleensä O(n log n). Joissakin tapauksissa parhaimmillaan ja pienillä datoilla insertion sort voi olla O(n). Ei-vertailupohjaisilla menetelmillä on usein lineaarinen aika O(n + k) tai O(nk), riippuen avainten arvoista ja jaon ominaisuuksista, ja ne voivat vaatia lisätilaa.

Käytännössä valinta riippuu datasta, muistista ja toteutuksen vakaudesta. Osa algoritmeista on in-place, kuten heapsort, ja toiset tarjoavat vakautta kuten mergesort. Järjestelyalgoritmien tunteminen auttaa optimoimaan suorituskyvyn suurten datasetien ja ulkoisiin tallennusratkaisuihin liittyvissä tehtävissä.