DD1320 Tillämpad Datalogi
Föreläsning 7: Sortering
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)
- Damerna först
- Quicksort
- Mergesort (Samsortering)
- Divide and conquer
- Räknesortering (Distribution count)
Urvalssortering (Selection sort)
Vi tänker oss att vi ska sortera en lista med N tal.
- Sök igenom listan efter minsta värdet. (N-1 jämförelser)
- Flytta det till första positionen. (Ett byte)
- Sök efter näst minsta värdet. (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 listan är från början. Tiden är alltså i stort
sett proportionell mot kvadraten på N. Man säger att komplexiteten
är O(N2).
6 |
13 |
5 |
2 |
1 |
3 |
7 |
8 |
10 |
12 |
4 |
9 |
11 |
1 |
13 |
5 |
2 |
6 |
3 |
7 |
8 |
10 |
12 |
4 |
9 |
11 |
1 |
2 |
5 |
13 |
6 |
3 |
7 |
8 |
10 |
12 |
4 |
9 |
11 |
|
 
 
 
 
 
|
def urvalssortera(data):
n = len(data)
for i in range(n):
minst = i
for j in range(i+1,n):
if data[j] < data[minst]:
minst = j
data[minst],data[i] = data[i], data[minst]
|
Urvalssorteringsanimation från Hong Kongs universitet.
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 listan 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 listan är nästan sorterad från början räcker det med några
få genomgångar och då blir bubbel snabbare än urval.
Bubbelsortanimation från universitetet i Oldenburg.
Insättningssortering (Insertion sort)
Denna metod känns särskilt naturlig
om man får värden ett efter ett (t ex
om dom läses in från en fil) och man vill sortera in dom i en
lista. Här sorterar vi in ett värde i taget på följande vis:
- Jämför med varje tidigare värde i listan.
- Om det nya värdet är mindre gör vi plats genom att flytta det tidigare värdet ett snäpp åt höger.
- Flytta fram så många värden som behövs för att sätta in nya värdet på rätt plats.
- Stoppa in det nya värdet.
Om alla värden redan finns i listan sorterar vi in ett värde i taget,
med början från det andra.
Komplexiteten är i allmänhet O(N2) men den är
lite snabbare än urvalssortering i praktiken eftersom en flytt
är snabbare än ett byte.
För att sortera in
ett nytt värde i en redan sorterad lista är
insättning bäst.
13 |
6 |
5 |
2 |
1 |
3 |
7 |
8 |
10 |
12 |
4 |
9 |
11 |
6 |
13 |
5 |
2 |
1 |
3 |
7 |
8 |
10 |
12 |
4 |
9 |
11 |
5 |
6 |
13 |
2 |
1 |
3 |
7 |
8 |
10 |
12 |
4 |
9 |
11 |
|
 
 
 
 
 
|
def insattningssortera(data):
n = len(data)
for i in range(1, n):
varde = data[i]
plats = i
while plats > 0 and data[plats-1] > varde:
data[plats] = data[plats-1]
plats = plats - 1
data[plats] = varde
|
Animation av insättningssortering från Indian Institute of Technology i Kanpur.
Damerna först
Den enklaste sorteringsuppgiften är att sortera om en personlista med
damerna först och den smarta algoritmen kallas
damerna-först-sortering.
- Sätt ett pekfinger i var ände av listan!
- 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. Listan 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 listan så att damerna kommer först.
- Sortera varje segment för sej.
def quicksort(data):
sista = len(data) - 1
qsort(data, 0, sista)
def qsort(data, i, j):
pivotindex = (i+j)//2
data[pivotindex], data[j] = data[j], data[pivotindex]
k = partitionera(data, i-1, j, data[j])
data[k], data[j] = data[j], data[k]
if k-i > 1:
qsort(data, i, k-1)
if j-k > 1:
qsort(data, k+1, j)
def partitionera(data, v, h, pivot):
while True:
v = v + 1
while data[v] < pivot:
v = v + 1
h = h -1
while h != 0 and data[h] > pivot:
h = h -1
data[v], data[h] = data[h], data[v]
if v >= h: break
data[v], data[h] = data[h], data[v]
return v
Komplexiteten blir i allmänhet O(N log N).
Det beror på att man kan dela listan på mitten log N gånger.
Exakt hur snabb den är beror på hur
man avgör vilka värden som ska vara damer. Om man tar det första värdet
i listan och utnämner det och alla mindre värden till damer, så blir
Quicksort mycket långsam för redan nästan sorterade listor! Det bästa
är att ta ut tre värden - 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.
Quicksortanimation från Aucklands universitet.
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 lista om man har
extrautrymme för att kopiera den till två andra hälften så långa listor.
Det här ger en rekursiv tanke!
- Dela listan i två hälften så långa listor.
- Sortera varje halva för sej.
- Samsortera till ursprungliga listan.
Komplexiteten blir O(N log N), lika snabb
som quicksort men kräver extra minnesutrymme. Om första halvan
av listan a ska samsorteras med andra halvan
kopierar man först över allting till hjälplistan 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(data):
if len(data) > 1:
mitten = len(data)//2
vensterHalva = data[:mitten]
hogerHalva = data[mitten:]
mergesort(vensterHalva)
mergesort(hogerHalva)
i, j, k = 0, 0, 0
while i < len(vensterHalva) and j < len(hogerHalva):
if vensterHalva[i] < hogerHalva[j]:
data[k] = vensterHalva[i]
i = i + 1
else:
data[k] = hogerHalva[j]
j = j + 1
k = k + 1
while i < len(vensterHalva):
data[k] = vensterHalva[i]
i = i + 1
k = k + 1
while j < len(hogerHalva):
data[k] = hogerHalva[j]
j = j + 1
k = k + 1
Mergesortanimation från North Carolina State University.
Divide and conquer
En kanske inte så sympatisk härskarteknik som går ut på
att så split mellan sina undersåtar för att rikta deras
misstro mot varandra istället för mot härskaren
kallas på engelska divide and conquer.
(På svenska säger vi söndra och härska, men det passar inte
lika bra här.)
Inom datalogi används detta uttryck för att beskriva en lösningsmetod
där man delar upp ett problem i två eller flera delproblem och löser
dessa var för sig. Delproblemen löses enklast med rekursion!
Quicksort och mergesort är två exempel på
divide-and-conquer-principen.
Räknesortering (Distribution count)
Om man vet att det bara finns ett litet antal nyckelvärden,
(t ex om man ska sortera Sveriges befolkning efter födelseår),
så är distributionsräkning oslagbart snabbt.
Det kräver att talen som sorteras in i listan hämtas från en annan
lista eller fil.
- Läs igenom filen och räkna hur många det finns av varje nyckelvärde.
- Dela in listan 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), men fungerar alltså bara om man har få nyckelvärden i förhållande till antalet data som ska sorteras.
Om man upprepar förfarandet för varje position (siffra eller bokstav) i de data som ska sorteras får man radixsortering!
3 |
4 |
3 |
3 |
5 |
3 |
5 |
3 |
5 |
4 |
5 |
3 |
4 |
3:6
4:3
5:4
3 |
3 |
3 |
    |
    |
    |
4 |
    |
    |
    |
    |
    |
    |
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.