Föreläsning 18: Sortering



Damerna först

Den enklaste sorteringsuppgiften är att sortera om en personarray med damerna först och den smarta algoritmen kallas damerna-först-sortering.
  1. Sätt ett pekfinger i var ände av arrayen!
  2. Rör fingrarna mot varandra tills vänstra fingret fastnat på en herre och högra fingret på en dam!
  3. Låt damen och herren byta plats!
  4. Upprepa från 2 tills fingrarna korsats!
Idén används i Quicksort, som är den snabbaste av alla sorteringsalgoritmer för normalt bruk.

Distributionsräkning (Distribution count)

Damerna-först utmärker sej genom att det bara finns två olika nyckelvärden. Om man vet att det bara finns ett litet antal nyckelvärden, till exempel 100 olika, är distributionsräkning oslagbart snabbt. Det kräver att talen som sorteras in i vektorn hämtas från en annan vektor eller fil. Komplexiteten blir O(N).

Quicksort

Damerna-först-algoritmen med två pekfingrar används i Quicksort. Först bestämmer man vilka (små) nyckelvärden som ska kallas damer. Resten kallas herrar och så utför man algoritmen. Vektorn delas alltså i två segment, det första med små värden, det andra med stora värden. Nu behöver man bara sortera segmenten var för sej. Det här är en rekursiv tanke!

Komplexiteten blir i allmänhet O(N log N). Det beror på att man kan dela vektorn på mitten log N gånger. Exakt hur snabb den är beror på hur man avgör vilka värden som ska vara damer. Ofta tar man det första talet i vektorn och utnämner det och alla mindre tal till damer. Då blir Quicksort mycket långsam för redan nästan sorterade vektorer! Det bästa är att ta ut tre tal - det första, det sista och något i mitten - och låta det mellersta värdet bestämma vad som är damer. Det kallas median-of-three. Man kan visa att komplexiteten då blir 1.4 N log N i genomsnitt.

Samsortering (Merge sort)

Om man har flera sorterade småfiler är det lätt att samsortera dom till en fil. Det här kan man också göra med en vektor om man har extrautrymme för att kopiera den till två andra hälften så långa vektorer. Det här ger en rekursiv tanke! Komplexiteten blir O(N log N), lika snabb som quicksort men kräver extra minnesutrymme.
.


^Upp till allmänna kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 6 februari 2005
Tekniskt stöd: <webmaster@nada.kth.se>