Redigerer Sorteringsalgoritme (avsnitt)

==Viktige sorteringsalgoritmer==
[[Fil:Insertion sort animation.gif|frame|Grafisk demonstrasjon av innstikksortering.]]

===Boblesortering===
{{utdypende|Boblesortering}}

Boblesortering (''bubble sort'') er en svært enkel sorteringsalgoritme som først og fremst brukes i pedagogisk sammenheng. Algoritmen begynner først i datasettet og sammenligner de to første elementene, og dersom det første er større enn det andre, bytter de plass. Dette gjøres med alle par av etterfølgende elementer gjennom hele datasettet. Deretter begynner algoritmen ved starten igjen, og repeterer inntil ingen elementer må byttes på siste gjennomgang. Boblesortering er svært lite effektivt og tidsbruken øker vanligvis kvadratisk med økende datamengde.

===Innstikksortering===
{{utdypende|Innstikksortering}}

Innstikksortering (''insertion sort'') er også en enkel sorteringsalgoritme. Den går gjennom datasettet fra begynnelsen og når den finner et tall som ikke står i rekkefølge tas det ut, de sorterte elementene som skal stå etter forskyves ett trinn til høyre og tallet settes inn på riktig plass. Så kan algoritmen fortsette med nye tall. Dette er en intuitiv metoden som mennesker ofte bruker, f.eks. når man sorterer kort. Også innstikksortering har kvadratisk tidsbruk, men metoden er likevel effektiv på små datamengder. Derfor brukes ofte varianter av innstikksortering i kombinasjon med mer avanserte sorteringsmetoder.<ref name="maus">Maus,Arne: [http://www.uio.no/studier/emner/matnat/ifi/INF2220/h08/undervisningsmateriale/Sortering-15og22okt2008-4ppage.pdf Sortering]. Forelesningsslides INF2220. Oktober 2008. Universitetet i Oslo.</ref>

===Skallsortering ===
Skallsortering (''shell sort'') er en forbedret variant av innstikksortering. Isteden for at algoritmen går fra ene siden sorterer den i "gap". Den kan for eksempel begynne med gap som er like store som halve datasettet, dette gir to operasjoner i første runde. Algoritmen sorterer det første tallet, tallet i midten og det siste tallet slik at de står riktig i forhold til hverandre. I neste runde kan den bruke gap på en fjerdedel av datasettet (fire operasjoner). Slik fortsetter den mens gapene blir mindre og mindre. Til slutt tar algoritmen alle tallene, men da er datasettet stort sett sortert. Med denne metoden flytter feilplasserte tall seg raskere gjennom datasettet enn ved tradisjonell innstikksortering. Algoritmen kan i verste fall bruke kvadratisk tid hvis tallene i data settet allerede er organisert slik at annen hvert tall er stort og annen hvert er lite. Dette kan imidlertid forhindres hvis man deler inn i gap ut fra andre systemer, f.eks. [[Fibonacci-tall]]ene, <math>2^k-1</math> eller andre tallsekvenser. Algoritmen ble beskrevet av Donald Shell i 1959.<ref>{{cite journal |last=Shell |first=D.L. |title=A high-speed sorting procedure |journal=Communications of the ACM |volume=2 |issue=7 |year=1959 |pages=30–32 |doi=10.1145/368370.368387}}</ref>

===Flettesortering===
{{utdypende|Flettesortering}}

I ren flettesortering (''merge sort'') deles datasettet først opp helt til det bare er ett tall i hver del. Algoritmen tar to og to deler, sammenligner de laveste ubrukte tallene og henter det tallet som er lavest. Tallene lastes over i nye delsett, og disse flettes også helt til man bare har ett datasett. Flettesortering er en effektiv algoritme med gjennomsnittlig kjøretid på [[stor O-notasjon|O]](''n'' log ''n''). Ofte brukes flettesortering i kombinasjon med andre sorteringsalgoritmer. Man lar da disse andre algoritmene sortere delmengder av datasettet for så å flette dem sammen. Tidligere var flettesortering mer interessant fordi man lettere kunne sortere direkte til harddisk med lavt minneforbruk. Med dagens datakapasitet er dette bare aktuelt i helt spesielle tilfeller.<ref name="maus" />

<pre>
Eksempel på utførelse, flettesortering av listen (8 3 9 13 12 2 14 10 5).

(8 3 9 13) || (12 2 14 10 5)
(8 3) || (9 13) || (12 2) || (14 10 5)
(8) || (3) || (9) || (13) || (12) || (2) || (14) || (10) || (5)
(3 8) || (9 13) || (2 12) || (5 10 14)
(3 8 9 13) || (2 5 10 12 14)
(2 3 5 8 9 10 12 13 14)
</pre>

===Haugsortering===
{{utdypende|Haugsortering}}
Haugsortering (''heap sort'') bruker datastrukturen [[heap]] til å organisere elementene i datasettet som skal sorteres. Algoritmen setter elementene inn i et [[tre (datastruktur)|komplett binært tre]]. Første fase av algoritmen ordner treet slik at alle nodene er større enn eller lik nodene under (eventuelt mindre). Deretter hentes største element ut og slettes og treet rettes opp. Heapsort er en effektiv algoritme i samme klasse som quicksort og mergesort. Det viktigste fortrinnet til heapsort er at den har en konstant kjøretid på [[stor O-notasjon|O]](''n'' log ''n''), også i dårlige tilfeller. Dette gjør at den er godt egnet i datasystemer der man ikke kan risikere forsinkelser. Det er også en fordel med tanke på sikkerhet fordi andre mye brukte algoritmer kan sakkes ned og kanskje bryte sammen ved at man legger inn store mengder data som gir dårlig ytelse. En ulempe med heapsort er at det er vanskelig å kjøre flere prosesser parallelt, man får med andre ord ikke fordel av å bruke mange prosessorer.<ref>Srivastava, Ashwin Prakash: [http://www.scribd.com/doc/7269318/Final-Heap-Sorting Heap Sort]</ref>

[[Fil:Sorting quicksort anim.gif|frame|Algoritmen kvikksortering (''quick sort'') sorterer en tallrekke. De horisontale linjene er pivotverdier.]]

===Kvikksortering ===
{{utdypende|Kvikksortering}}

Kvikksortering (''quick sort'') er et eksempel på en såkalt splitt-og-hersk-algoritme. Quicksort begynner med å velge en pivot, et tilfeldig tall x, i datasettet, og så sortere settet i tre deler, en del for de tallene som er mindre enn x, en del for de som er like store, og en del for dem som er større. Deretter gjentas operasjonen på de tallene som var større og de tallene som var mindre helt til alt er sortert og de kan settes opp i rekkefølge. Quicksort er basert på [[rekursjon]]. Gjennomsnittlig tidsbruk for quicksort er [[stor O-notasjon|O]](''n'' log ''n''), men i verste fall kan den bruke [[stor O-notasjon|O]](''n''<sup>2</sup>). Dette skjer for eksempel hvis man alltid bruker siste tall i settet som pivot og man prøver å sortere et datasett som allerede er sortert. Dette problemet kan utbedres ved å velge medianen av det første, det midterste og det siste tallet i datasettet. Quick sort er ikke spesielt effektivt på svært små datasett, derfor gjør man det ofte i praksis slik at når datasettene er delt ned til rundt ti elementer sorteres de ved innstikksortering. Quick sort er en svært mye brukt algoritme og fungerer godt i de fleste situasjoner.<ref name="maus" /><ref>Goodrich, Michael T./ Tamassia, Roberto: Data Structures & Algorithms in Java. John Wiley & Sons, Inc. 2006.</ref>

===Bøttesortering===
Bøttesortering (''bucket sort'') er egnet på datasett der et begrenset antall verdier går igjen. Algoritmen begynner med å opprette "bøtter" for hver verdi, den går så gjennom datasettet og fordeler verdiene den finner i de ulike "bøttene". Den kan så eventuelt gå over alle bøttene og sortere innenfor hver enkelt bøtte. Til slutt setter den sammen datasettet igjen ved å gå systematisk gjennom bøttene. En variant av bøttesortering er å ta ut i bøttene, sette tilbake og så bruke innstikksortering til å få datasettet helt ordnet. I beste fall kan bøttesortering gi lineær tidsbruk – [[stor O-notasjon|O]](''n''), noe som er bedre enn den teoretiske grensen for alle sammenligningsbaserte sorteringsalgoritmer. I verste fall kan imidlertid tidsbruken være kvadratisk, [[stor O-notasjon|O]](''n''<sup>2</sup>).

===Radixsortering===
Radixsortering (''radix sort'', «[[grunntall]]-sortering») er i likhet med bøttesortering egnet i datasett der et begrenset antall verdier går igjen og brukes til å sortere heltall. En vanlig brukt implementasjon av radix-sortering er å begynne med den minst viktige verdien, det vil si sifferet lengst til høyre i et tall, og fordele dataene i "hauger" ut fra dette. Deretter slås datasettet sammen og man sorterer på det nest viktigste sifferet. Radix-sortering er i mange tilfelle den mest effektive kjente sorteringsalgoritmen.<ref name="maus" />