Sorteringsalgoritme

Fra Wikipedia, den frie encyklopædi

Sorteringsproblemet handler om at permutere (omordne) elementerne i en given liste med n elementer <x₁,x₂, ... , x_n> til listen <x₁’,x₂’, .. , x_n’> således, at x₁' ≤ x₂’ ≤ ... ≤ x_n’. Elementerne i listen er typisk tal fra mængden af de naturlige tal, men generelt kan elementerne i listen være al mulig objekter; så længe disse objekter kan sammenlignes med hinanden og opstilles i en kronologisk rækkefølge. Sortering er det mest kendte problem indenfor Algoritmik og er et fundamental operation indenfor datalogi området, hvor det bruges i mange programmerings projekter. Der er igennem tiden udviklet mange sorteringsalgoritmer, hvor de både afviger i deres beregningskompleksitet og den fremgangsmåde de anvender til løsningen af problemet.

Sorteringsalgoritmerne kan opdeles i forskellige grupper. De mest kendte algoritmer er dem som hører under gruppen sammenlignings sortering (eller sammenligningsbaseret sortering). ”Nedre grænsen for sammenlignings sortering” er en overskrift for et bevis der udsiger, at enhver sammenlignings sorterings algoritme kræver mindst n log n (Ω(n log n)) sammenligninger i værste tilfælde. Gruppen af sammenlignings sortering består af følgende algoritmer:

• Indsættelsessortering
• Quicksortering
• Boblesortering
• Flettesortering
• Udtagelsessortering
• Hopsortering

Den anden gruppe består af de sorterings algoritmer, der har en linære beregningskompleksitet. Disse algoritmer sorter en liste uden at sammenligne elementerne med hinanden. Denne gruppe består af følgende algoritmer:

• Tællesortering
• Radixsortering
• Bucketsortering

Indenfor grafteori findes der også en bestemst sorterings algoritme, der sorter knuderne i grafen i en bestemt rækkefølge. Algoritmen kaldes for topologisksortering.