Sorteringsalgoritme
From Wikipedia, the free encyclopedia
I informatikken og matematikk er en sorteringsalgoritme en algoritme som ordner elementer i en bestemt rekkefølge. De vanligste rekkefølgene er numerisk rekkefølge og alfabetisk rekkefølge. Effektiv sortering er viktig for mange andre algoritmer, som f.eks. søke- og flettealgoritmer, som krever sorterte data for å fungere riktig. Ofte er det også nyttig for å lage menneskelig lesbar utskrift.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif)
![Boblesortering redigert farge](http://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Bubblesort-edited-color.svg/320px-Bubblesort-edited-color.svg.png)
Formelt sett må resultatet av en sortering tilfredsstille to betingelser; elementene må stå i en økende rekkefølge, dvs. alle elementer må være like stort eller større enn det foregående ut ifra en gitt sammenligningsfunksjon, og resultatet må være en permutasjon av inn-dataene.
Det har vært forsket på sorteringsproblemet siden datamaskinens barndom, kanskje fordi det er et grunnleggende og trivielt problem, samtidig som det er utfordrende å løse effektivt. Selv om mange betrakter problemet som løst, blir nye og anvendelige sorteringsalgoritmer publisert i dag. Viktige faktorer i vurderingen av effektiviteten til en algoritme er beste, verste og gjennomsnittlige tidsbruk og minnebruk.