sorteringsalgoritme
Varianter
Det finnes mange kjente sorteringsalgoritmer, blant andre kvikksortering, flettesortering, innstikksortering og boblesortering. I praksis brukes ofte varianter av disse, og i nyere tid har flere og flere applikasjoner tatt i bruk en ganske ny algoritme, timsortering, som er en variant av flettesortering og innstikksortering, med noen heuristikker.
Sortering av lister
Den mest vanlige bruken av sorteringsalgoritmer er å sortere en liste. Hvis man leter etter et objekt, er det ofte enklere å finne frem dersom listen av objekter er sortert, som innholdsfortegnelser, telefonkataloger og leksikon.
Listen kan sorteres enten etter tallverdi eller alfabetisk, og enten i stigende eller synkende rekkefølge. Et eksempel er når man sorterer en liste av filer i en katalog enten etter filnavn (alfabetisk), etter når filene ble sist endret (dato) eller etter filstørrelse (antall bytes).
Eksempel på sortering av en liste av tall i stigende rekkefølge:
[7, 2, 9, 4, 1, 6] → [1, 2, 4, 6, 7, 9]
En sorteringsalgoritme kalles stabil dersom den bevarer den opprinnelige ordningen av like elementer. Det vil for eksempel si at dersom man sorterer en liste av personer på fødselsår, så vil de som har samme fødselsår komme ut i samme rekkefølge som de kom inn. Stabilitet er en viktig egenskap ved sorteringsalgoritmer fordi det gjør det mulig å sortere på flere egenskaper. For eksempel kan man da sortere en liste av mennesker først på alder, og deretter alfabetisk.
| Alder | Navn |
|---|---|
| 15 | Ali |
| 15 | Hagen |
| 15 | Lund |
| 15 | Ruud |
| 16 | Ahmed |
| 16 | Bakken |
| 16 | Dahl |
| 16 | Eide |
| 16 | Lie |
| 16 | Moen |
| 16 | Nguyen |
| 17 | Berg |
| 38 | Hansen |
En tabell som først blir sortert på navn og deretter på alder vil ha egenskapen at den er sortert på alder og dernest på navn.
Sammenligningsalgoritmer
Det finnes et titall populære sammenligningsalgoritmer, men de mest kjente er boblesortering, flettesortering og kvikksortering. De fungerer på ganske forskjellige måter.
Boblesortering
Boblesortering (engelsk bubble sort) fungerer ved at man går gjennom listen av elementer og ser på to og to elementer som ligger ved siden av hverandre. Hvis de er i feil rekkefølge, så bytter man om på dem og går videre. Etter at man har gått gjennom listen én gang, vil det største tallet være sist i listen. Så må man gjenta prosessen for å få det nest største tallet nest sist i listen, og så må man gjenta prosessen for å få det tredje største tallet på tredje siste plass, og så videre. Hvis listen har N elementer, betyr dette at algoritmen går gjennom hele listen N ganger, altså blir det gjort N2 mange sammenligninger. Det vil si at algoritmen har N2 kjøretid.
Flettesortering
Flettesortering (engelsk merge sort) er en rekursiv algoritme som deler listen i to halvdeler og sorterer hver for seg selv, og som til slutt fletter to sorterte lister sammen. En matematisk analyse av denne algoritmen viser at den bare trenger å gjøre N log N mange sammenligninger, det vil si at den gjør mange færre operasjoner enn boblesortering.
Kvikksortering
Kvikksortering (engelsk quick sort) er en algoritme som også deler listen i to, men i stedet for at den deler den i to like deler, så deler den listen i to deler som kan ha (hvis man er uheldig) svært forskjellig størrelse. Denne algoritmen har forventet kjøretid N log N, men i verste fall bruker den N2 sammenligninger. Den lengste kjøretiden får man ved å kjøre algoritmen på en liste som allerede er sortert, men sortert feil vei.
Andre metoder
Som beskrivelsene over tilsier, kan man ikke sortere en liste med N elementer ved å bruke færre enn N log N sammenligninger, men i noen tilfeller kan man slippe å sammenligne. Dersom man for eksempel ønsker å sortere alle mennesker i Norge på alder, så kan man putte alle som er 0 år i en «bøtte» vi kaller for Bøtte 0, alle som er 1 år i Bøtte 1, og så videre helt til alle er plassert i bøtter. Deretter kan man skrive ut alle som er i Bøtte 0, etterfulgt av alle i Bøtte 1, etterfulgt av alle i Bøtte 2, og så videre. Denne algoritmen har et tidsforbruk på N tid, som vil si at man kan sortere alle mennesker i Norge på et par millisekunder. Denne algoritmen kalles bøttesortering (engelsk bucket sort).
Kjøretid
En viktig egenskap ved en sorteringsalgoritme er hvilken kjøretid den har, det vil si hvor lang tid den bruker på å sortere en liste med N elementer. Ingen vanlig sorteringsalgoritme kan bruke mindre enn N log N tid, og de fleste bruker nettopp N log N tid. Noen unntak er innstikksortering og boblesortering, som begge bruker N2 tid.
Forskjellen på disse kjøretidene er ganske ekstrem. På ett sekund kan flettesortering sortere 10 millioner elementer, mens boblesortering kun klarer 30 000. Dette vil si at dersom man for eksempel vil sortere alle mennesker i Norge på alder og navn, så kan man gjøre dette på under ett sekund med flettesortering. Velger man boblesortering, vil det ta syv timer.
Algoritmer deles inn i kompleksitetsklasser ut fra hvor lang kjøretid de har.
Les mer i Store norske leksikon
Kommentarer
Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.
Du må være logget inn for å kommentere.