Sorteringsalgoritm

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-07) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Sorteringsalgoritm är en algoritm avsedd att sortera data, till exempel för att sortera en lista med namn eller en mängd poster i en databas efter en önskad nyckel. Vanliga tillämpningar för sorteringsalgoritmer är användarvänlig presentation av data och som subrutin för att möjliggöra uppsnabbning eller förenkling av andra algoritmer.

Egenskaper

Vid jämförelser av sorteringsalgoritmen är det några egenskaper som främst brukar diskuteras.

• Tidskomplexitet: Hur effektiv är algoritmen som funktion av antalet element, n, som ska sorteras? Framför allt är det komplexiteten i värsta fallet eller den förväntade (genomsnittliga) komplexiteten som är intressant. Oftast används en kostnadsmodel där bara jämförelser räknas eftersom det gör diskussionen generell, men i fall där man vet mycket om de data som ska sorteras kan det vara intressant att titta på mer allmänna modeller för att kunna dra nytta av att man till exempel vet att det är små heltal man sorterar.
• Minnesanvändning: Behövs det mer minne än för de element som ska sorteras? Vissa algoritmer behöver plats för mellanlagring och andra kan sortera precis i det minnesutrymme som elementen redan använder.
• Stabilitet: Om det är en lista med poster som ska sorteras efter en nyckel kan det vara intressant att bibehålla den ordning man redan har på elementen. Antag att en lista med persondata ska sorteras efter födelseåret och personposterna redan ligger i namnordning, då vore det bra om sorteringen bibehöll namnordningen för alla som var födda samma år. En icke-stabil sorteringsalgoritm garanterar inte detta.

Ett antal algoritmer

• Bubbelsortering
• Bucket sort
• Heapsort
• Insättningssortering
• J sort
• Merge sort
• Quicksort
• Radix sort
• Random sort
• Shell sort
• Urvalssortering