Sorteringsalgoritme

Algoritmen haugsortering (heap sort) ordner et datasett.

Boblesortering redigert farge

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.

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.

Tidsbruk

Som mål for en algoritmes effektivitet brukes ofte stor O-notasjon. Ut fra denne notasjonen kan man i grove trekk se hvordan algoritmens tidsbruk endres med økende datamengde.

De enkleste sorteringsalgoritmene har ofte en tidsbruk som i grove trekk øker kvadratisk med stigende datamengde – O(n²). Dette gjelder boblesortering og innstikksortering. Shellsortering fungerer på en tilsvarende måte, men er tilpasset slik at man vanligvis oppnår noe bedre ytelse. Den teoretiske grensen for tidsbruk for en sammenligningsbasert sortering ligger på O(n log n), og dette kan oppnås blant annet av mergesort, quicksort og heapsort. I enkelte tilfeller kan man oppnå høyere ytelse en dette, det gjelder først og fremst i datasett med begrenset omfang, for eksempel hvis man skal sortere en million siffer som alle er mellom 0 og 1000. Man kan da komme ned i lineær tidsbruk O(n) ved hjelp av blant annet bøttesortering og radix-sortering.

Viktige sorteringsalgoritmer

Grafisk demonstrasjon av innstikksortering.

Boblesortering

Utdypende artikkel: 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 artikkel: 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.

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-tallene, $2^{k}-1$ eller andre tallsekvenser. Algoritmen ble beskrevet av Donald Shell i 1959.

Flettesortering

Utdypende artikkel: 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å 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.

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)

Haugsortering

Utdypende artikkel: Haugsortering

Haugsortering (heap sort) bruker datastrukturen heap til å organisere elementene i datasettet som skal sorteres. Algoritmen setter elementene inn i et 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å 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.

Algoritmen kvikksortering (quick sort) sorterer en tallrekke. De horisontale linjene er pivotverdier.

Kvikksortering

Utdypende artikkel: 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 O(n log n), men i verste fall kan den bruke O(n²). 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.

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 – O(n), noe som er bedre enn den teoretiske grensen for alle sammenligningsbaserte sorteringsalgoritmer. I verste fall kan imidlertid tidsbruken være kvadratisk, O(n²).

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.