Sorttausalgoritmit

Sorttausalgoritmit eli lajittelualgoritmit ovat tietojenkäsittelytieteessä algoritmeja, jotka järjestävät listan tai taulukon elementtejä ennalta määritellyn järjestyksen mukaan. Yleisimpiä järjestysperusteita ovat numeerinen tai aakkosjärjestys. Lajittelualgoritmeilla on keskeinen rooli monissa tietojenkäsittelyn sovelluksissa, kuten tietokantojen kyselyissä ja hakualgoritmeissa.

On olemassa lukuisia erilaisia lajittelualgoritmeja, joista jokaisella on omat vahvuutensa ja heikkoutensa suorituskyvyn ja muistinkäytön suhteen. Esimerkkejä yleisistä lajittelualgoritmeista ovat kuplalajittelu (bubble sort), valintalajittelu (selection sort), lisäyslajittelu (insertion sort), pikalajittelu (quick sort), yhdistämislajittelu (merge sort) ja kekolajittelu (heap sort). Algoritmin valinta riippuu usein käsiteltävän datan koosta ja ominaisuuksista sekä vaaditusta tehokkuudesta.

Lajittelualgoritmien tehokkuutta analysoidaan yleensä niiden aikakompleksisuuden perusteella, joka kuvaa algoritmin suoritusajan riippuvuutta syötteen koosta. Aikakompleksisuutta ilmoitetaan usein Big O -notaatiolla, kuten O(n^2) tai O(n log n). Tehokkaimmat lajittelualgoritmit saavuttavat O(n log n) aikakompleksisuuden pahimmassa tapauksessa. Muistikompleksisuus puolestaan kuvaa algoritmin käyttämää muistimäärää. Jotkin algoritmit vaativat lisämuistia, kun taas toiset lajittelevat datan paikallaan ilman merkittävää lisämuistin tarvetta.