Sortering är en av dom vanligaste uppgifterna för ett program.
Här följer en beskrivning av några sorteringsalgoritmer.
Urvalssortering (Selection sort)
Bubbelsortering (Bubble sort)
Insättningssortering (Insertion sort)
Shellsort (uppfunnen av Donald Shell)
Damerna först
Quicksort
Samsortering (Mergesort)
Distributionsräkning (Distribution count)
Trappsortering (Heapsort)
Radixsortering
Urvalssortering (Selection sort)
Vi tänker oss att vi ska sortera en vektor med N tal.
Sök igenom vektorn efter minsta talet. (N-1 jämförelser)
Flytta det till första positionen. (Ett byte)
Sök efter näst minsta talet. (N-2 jämförelser)
Flytta det till andra positionen. (Ett byte)
- - -
Totalt krävs N(N-1)/2 jämförelser och N-1 byten, helt oberoende av
hur pass osorterad vektorn är från början. Tiden är alltså i stort
sett proportionell mot kvadraten på N. Man säger att komplexiteten
är O(N2).
Bubbelsortering (Bubble sort)
En något smartare metod än urvalssortering är denna:
Byt första och andra om dom står i fel ordning. (En jämförelse, ett byte)
Byt andra och tredje om dom står i fel ordning. (En jämförelse, ett byte)
- - -
Bubbla igenom vektorn gång på gång tills inga byten sker.
Totalt krävs i värsta fall N(N-1)/2 jämförelser och lika många byten.
Men om vektorn är nästan sorterad från början räcker det med några
få genomgångar, och då blir bubbel snabbare är urval.
Insättningssortering (Insertion sort)
Denna metod känns särskilt naturlig
om man hämtar talen ett efter ett från en fil och sorterar in dom i en
vektor.
Jämför nya talet med sista talet i vektor.
Om nya är större, lägg det sist i vektorn.
Annars, putta ner sista talet ett pinnhål och jämför igen.
Putta ner så många tal som behövs för att sätta in nya talet på rätt plats.
Upprepa för varje nytt tal.
Insättning fungerar också om talen finns i vektorn från början. Efter
k insättningar är vektorsegmentet
v[1]...v[k] ordnat och
v[k+1] är det nya talet som ska sättas in.
Komplexiteten är i allmänhet O(N2) men för att sortera in
ett nytt värde i en redan sorterad vektor är
insättning den snabbaste algoritmen.
"Insättningssortering av vektorn a"
# Först finns bara a[0], sedan insätts a[1], sedan a[2] osv.
# Om a[j] som sätts in bör ligga på plats a[i] måste alla
# mellanliggande element a[i]...a[j-1] puttas ett steg.
for j in range(1,len(a)):
aj=a[j]
i=j
while i>0 and aj<a[i-1]:
a[i]=a[i-1]
i=i-1
a[i]=aj
Shellsort
Insättningssortering byter bara plats på intilliggande element.
Om t ex det minsta värdet ligger sist kommer det att ta N steg
innan det hamnat på rätt plats. Shellsort är en förbättring
av insättningssortering där man byter plats på element som ligger längre
ifrån varann.
Idén är att man sorterar vart h:te element för en serie
minskande h-värden (som måste avslutas med h=1).
"Shellsort av vektorn a"
# Jämför med insättningssortering!
h = len(a)//2
while h>0:
for j in range(h,len(a)):
aj = a[j]
i = j
while i>0 and aj<a[i-h]:
a[i] = a[i-h]
i=i-h
a[i]=aj
if h==2: h=1
else: h=int(h/2.2)
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.
Sätt ett pekfinger i var ände av arrayen!
Rör fingrarna mot varandra tills vänstra fingret fastnat på en
herre och högra fingret på en dam!
Låt damen och herren byta plats!
Upprepa från 2 tills fingrarna korsats!
Idén kan utvecklas till Quicksort, som är den snabbaste av alla
sorteringsalgoritmer.
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!
Bestäm vilka värden som ska kallas damer.
Partitionera vektorn så att damerna kommer först.
Sortera varje segment för sej.
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 (Mergesort)
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!
Dela vektorn i två hälften så långa vektorer.
Sortera varje halva för sej.
Samsortera till ursprungliga vektorn.
Komplexiteten blir O(N log N), lika snabb
som quicksort men kräver extra minnesutrymme. Om första halvan
av vektorn a ska samsorteras med andra halvan
kopierar man först över allting till hjälpvektorn b
och sorterar sedan tillbaka från b till a.
Detta förfarande kallas merge och programmeras lämpligen som en
egen metod.
def mergesort(a,left,right):
if left+1<right:
center = (left + right)//2
mergesort(a,left,center)
mergesort(a,center,right)
merge(a,left,center,right)
def merge(a,left,center,right):
b[left:right]=a[left:right]
i=left
j=center
k=left
while i<center and j<right:
if b[i]<b[j]:
a[k]=b[i]
i=i+1
else:
a[k]=b[j]
j=j+1
k=k+1
if i==center:
while j<right:
a[k]=b[j]
j=j+1
k=k+1
else:
while i<center:
a[k]=b[i]
i=i+1
k=k+1
Distributionsräkning (Distribution count)
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.
Läs igenom filen och räkna hur många det finns av varje nyckelvärde.
Dela in vektorn i lagom stora segment för denna distribution.
Läs filen igen och lägg in varje värde i sitt segment.
Komplexiteten blir O(N).
Heapsort
Om man stoppar in N tal i en trappa och sedan hämtar ut dom ett efter ett
får man dom sorterade. Komplexiteten för denna heapsort
blir O(N log N),
alltså av lika god storleksordning som quicksort. Visserligen är
quicksort lite snabbare, men heapsort har inte quicksorts dåliga
värstafallsbeteende. och så kan ju en heap användas till andra
saker än sortering också.
"Heapsort av orden på en fil"
heap = Heap(16)
for ord in open("bibel.txt").read().split():
heap.put(ord,ord)
while not heap.isempty():
print heap.get()
Radixsortering
Kallas också hålkortssortering av oss som var med på
hålkortsmaskinernas tid. Passar bäst när alla nycklar
har samma längd, som tiosiffriga personnummer. Först
sorteras korten i tio buntar efter sista
siffran. Sen lägger man ihop buntarna och gör en ny
sortering efter näst sista siffran etc. Till slut är
faktiskt alla korten ordnade och det efter bara O(N)
jämförelser, nämligen kN, där k
är antalet siffror.
Nu är det ju inte frågan om hålkortsbuntar längre utan
snarare om vektorer i minnet. Sorteringen kan då göras
med distributionsräkning, eftersom det i varje sortering
bara finns tio olika nyckelvärden.
Det går lika bra att sortera strängar, enda skillnaden
är att det finns tjugonio nyckelvärden i varje sortering.
En sträng kan ju uppfattas som ett tal skrivet med basen
29 och siffrorna A-Ö. Radix betyder just
bas i ett talsystem.
Sortering av större mängder data
Alla metoderna ovan förutsätter att de data som ska sorteras
kan lagras i primärminnet. Om så inte är fallet får man ta
till extern sortering men det ingår inte i den här kursen.
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 26 januari 2006
Tekniskt stöd: <webmaster@nada.kth.se>