SimReal - Sortering - Quicksort

Vi ønsker å sortere en tallmengde i stigende rekkefølge.
Hvis tallmengden er stor, kan det være hensiktsmessig med en klar strategi for denne sorteringen, spesielt mht en eventuell maskinell sorteringsbehandling.
På denne siden vises et eksempel på en slik sorterings-strategi, den såkalte 'quicksort'.
Bortsett fra noen spesial-tilfeller, er quicksort den raskeste generelle sorterings-algoritmen.

Som eksempel på quicksort tenker vi oss den usorterte tallmengden bestående av tallene
51-33-17-59-70-87-12-62-90-22-78-60.
Disse tallene ønsker vi å sortere i stigende rekkefølge. Informasjonen under punktene 1, 2 og 3 i figuren til venstre viser strategien i quicksort.
Vi plukker ut ett av tallene, kalt ref (f.eks. det første 51), og sørger for at dette tallet kommer på korrekt plass i tabellen, dvs etter at ref er plassert skal alle tall til venstre for ref være mindre enn ref og alle tallene til høyre for 51 skal være større enn ref (vi kan her også håndtere likhet mellom tall).
Deretter gjentas prosessen på hver av de to halvdelene som ref (etter korrekt plassering av ref) deler tabellen i.

For å få vårt første valgte tall (her 51) på korrekt plass i tabellen, gjøres følgende:
Vi tar vare på det første valgte tallet (her 51) i en variabel kalt ref, slik at tallet 51's opprinnelige posisjon blir ledig.
Deretter scanner vi tabellen fra høyre inntil vi påtreffer første tall som er mindre enn ref.
Dette tallet flytter vi til den ledige plassen (plassen hvor ref opprinnelig befant seg).
Deretter scanner vi tabellen fra venstre inntil vi påtreffer første tall som er større enn ref.
Dette tallet flytter vi til den ledige plassen.
Scanningen fortsetter nå etter tur fra høyre og venstre igjen, inntil høyre- og venstre-scanningen møtes.
Tallet ref plasseres i den ledige posisjonen, og er nå kommet på korrekt plass i tabellen.

Den samme prosedyren gjentas nå på hver av de to halvdelene som tallet ref deler tabellen i.

Det er velkjent at en slik form for gjentagende 'to-deling' er meget effektiv i ulike data-prosesser.

Her vises første halvdel av en algoritme for quicksort.
De to scanne-prosedyrene (while-sløyfer) samt etterfølgende plassering av tallet ref vises tydelig.

Her vises andr halvdel av quicksort-algoritmen.
For å kunne gjenta foregående prosess på hver av de to halvdelene som tallet ref deler tabellen i, lagres opplysninger (endepunkter) om en av disse to halvdelene (fortrinnsvis den største halvdelen, dette for å minimalisere risikoen for stack-overflow), mens foregående prosess gjentas på den andre av de to nevnte halvdelene.
Denne to-delingen gjentas nå inntil hele tabellen er sortert.

Her vises første halvdel av en rekursiv versjon av algoritme for quicksort.
Rekursjon er nærliggende siden prosessen for hver av de genererte halvdelene er lik prosssen for håndtering av den opprinnelige tabellen.
Selv om rekursjon er programmerings-besparende, skal vi være oppmerksom på at rekursjon sammenlignet med iterasjon vanligvis er mer ressurs- (herunder tid-) krevende.

Her vises andre halvdel av den rekursive algoritmen for quicksort.
Rutinen kaller opp seg selv (quickSort), men med stadig nye ende-parametre svarende til nye to-delinger.