Sorteringsalgoritm
Wikipedia
Sorteringsalgoritm, algoritm avsedd att sortera data, tex 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.
[redigera] 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 tex vet att det är små heltal man sorterar.
- Minnesanvändning: Behövs det mer minne är för dom element som ska sorteras? Vissa algoritmer behöver plats för mellanlagring och andra kan sorta 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 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.
[redigera] Ett antal algoritmer
- Bubble sort
- Bucket sort
- Dubbelriktad bubble sort
- Heap sort
- Insertion sort
- J sort
- Merge sort
- Quicksort
- Radix sort
- selection sort
- Tre vägs radix quicksort
