Från Rilpedia

Sorteringsalgoritm, 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.

Allt eftersom datavetenskapen har utvecklats har allt fler sorteringsalgoritmer tillkommit. Ingen algoritm är överlägsen de andra i alla situationer.

Egenskaper

Vid jämförelser av sorteringsalgortmen ä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 beräkningsmodell där bara jämförelser räknas eftersom det gör diskussionen generell, men i fall där man vet mycket om dom 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
• Dubbelriktad bubble sort
• Heap sort

• J sort
• Merge sort
• Quicksort
• Radix sort
• Insättningssortering (Insertion sort)
• Urvalssortering (Selection sort)
• Tre vägs radix quicksort