Sorteringsalgoritmen

Sorteringsalgoritmen är en term som beskriver metoder för att ordna en samling element i en viss ordning, oftast stigande eller fallande. Att sortera data underlättar vidare bearbetning, jämförelser och flera algoritmiska steg där ordningen är viktig.

Sorteringsalgoritmer delas vanligen in i jämförbaserade och icke-jämförbaserade sorter. Jämförbaserade sorteringar avgör ordningen genom att jämföra två element. Exempel är snabbsortering (quicksort), mergesort, heapsort, insättningssortering (insertion sort) och urvalsortering (selection sort). Generellt har effektiva jämförbaserade sorteringar i genomsnitt O(n log n) tid. Snabbsortering kan i sämsta fall bli O(n^2), medan mergesort och heapsort behåller O(n log n) i alla fall. Stabilitet varierar mellan algoritmer; mergesort är vanligtvis stabil, medan snabbsort och heapsort ofta inte är det i standardimplementationer.

Icke-jämförbaserade sorteringar uppnår ofta linjär tid när nycklarna är inom ett begränsat intervall eller består av ett fåtal siffror. Exempel inkluderar räknesortering (counting sort), radix sort och bucket sort. Dessa metoder kräver ofta extra minne och passar inte alltid för allmänna data.

Valet av sorteringsalgoritm beror på dataegenskaper, krav på stabilitet och minnesanvändning samt på om data redan är delvis sorterade. Genom att känna till tidskomplexitet och stabilitet kan man välja en lämplig algoritm för uppgiften.