Datastructuren
Quicksort en andere
sorteermethoden
College 3
1
Vandaag
 Quicksort
 Randomized quicksort
 Meer over analyse van algoritmen
 Heaps en heapsort
2
Datastructuren
Quicksort
 Verdeel en heers paradigma
 Idee is:
 Kies een element uit de array, zeg x
 Splits de array in drie stukken:
• Alles in 1e stuk is ≤ x
• 2e stuk is het element x
• Alles in 3e stuk is ≥ x (of >)
 Sorteer recursief het eerste stuk
 Sorteer recursief het derde stuk
 Klaar!
3
Opmerking
 In onze beschrijving gaan we er van uit dat
alle elementen verschillend zijn
 Als er gelijke elementen zijn, werkt het ook,
maar moet je iets beter opletten in de
analyse (zelfde code kan gebruikt worden)
4
Datastructuren
Quicksort: Eén
PARTITION
5
Datastructuren
Splitsen
Partition(A,p,r)
 {Input is array A met
indexwaardes van p tot
en met r}
 {Output: waarde q met
p ≤ q ≤ r zodat A[p..r]
een permutatie is van
input, en als p ≤ i < q
dan geldt A[i] ≤ A[q] en
als q < i ≤ r dan geldt
A[i] > A[q]}
 …
6
 Methode partitioneert
array A[p…r]
 Returnwaarde is plek
waar “splitselement”
terechtgekomen is
 Splitselement heet
pivot en nemen we nu
als element dat op A[r]
staat
Partition
 Code in boek is subtiel
Allemaal ≤
p
Allemaal >
i i+1
r
j-1 j
Gebied waar we nog
aan werken
7
pivot
Pseudocode Partition
Partition(A,p,r)
 pivot = A[r];
 i = p – 1;
 for j = p to r – 1 do
 {*}
 if A[j] ≤ pivot
 then
• i ++;
• Verwissel A[i] en A[j]
 Verwissel A[i+1] en
A[r];
 return i+1;
8
 Invariant: bij * geldt
voor elke k, p ≤ k ≤ r:
1. Als p ≤ k ≤ i, dan A[k]
≤ pivot
2. Als i+1 ≤ k ≤ j – 1,
dan A[k] > pivot
3. Als k=r, dan
A[k]=pivot
Pseudocode Partition
Partition(A,p,r)
 pivot = A[r];
 i = p – 1;
 for j = p to r – 1 do
 {*}
 if A[j] ≤ pivot
 then
• i ++;
• Verwissel A[i] en A[j]
 Verwissel A[i+1] en
A[r];
 return i+1;
9
 Invariant: bij * geldt
voor elke k, p ≤ k ≤ r:
1. Als p ≤ k ≤ i, dan A[k]
≤ pivot
2. Als i+1 ≤ k ≤ j – 1,
dan A[k] > pivot
3. Als k=r, dan
A[k]=pivot
 Merk op:
 Initieel geldt
invariant: triviaal
 Invariant blijft gelden
 Bij terminatie …
Partition na de loop
Allemaal ≤
p
Allemaal >
r
i i+1
 En dan verwisselen we A[i+1] en A[r]
Allemaal ≤
p
10
Allemaal >
i+1
r
Looptijd partition
Partition(A,p,r)
 pivot = A[r];
 i = p – 1;
 for j = p to r – 1 do
 {*}
 if A[j] ≤ pivot
 then
• i ++;
• Verwissel A[i] en A[j]
 Verwissel A[i+1] en
A[r];
 return i+1;
11
 Lineair: Θ(r-p+1)
 Inspectie van
loopstructuur
Quicksort: Twee
CODE EN EERSTE
ANALYSE
12
Datastructuren
Quicksort
Quicksort(A, p, r)
 {Sorteert het deel van de array A[p…r]}
 if p < r
 then
 q = Partition(A, p, r)
 Quicksort(A, p, q-1)
 Quicksort(A, q+1, r)
13
r
p
q
Allemaal ≤
p
14
Allemaal >
r
Hoeveel tijd kost Quicksort?
 In het slechtste geval gaat het erg
langzaam…
 Bekijk een gesorteerde rij:
 We splitsen in stukken van grootte n – 1; 1; 0
 En de volgende keer in stukken van grootte n-2;
1; 0
 Etc.
 Dus: cn+ c(n-1)+ c(n-2)+ c(n-3) + … +3c+2c+c
= c n(n+1)/2 stappen
 Op een gesorteerde rij: Ο(n2) stappen
15
Analyse met recurrente betrekkingen
 Schrijf: T(n) is aantal stappen van Quicksort
op gesorteerd array met n elementen
 T(n)
= T(n-1)+T(0) + Ο(n)
= T(n-1)+ Ο(n)
= Ο(n2)
Andere constantes
Met inductie naar n
16
Quicksort voor aartsoptimisten
 Als we echt geluk hebben, splitst Quicksort
altijd precies middendoor en gaan we in
recursie op twee stukken van hooguit n/2
elementen
 Zelfde analyse als bij Mergesort geeft
Ο(n lg n) tijd
17
log n niveau’s
18
Beste geval analyse van Quicksort met
recurrente betrekkingen
 Stel T(n) is het beste geval van de looptijd
van Quicksort op een array met n
elementen
 T(n) ≤ 2*T(n /2) + O(n) (*)
 T(n) = O(n lg n)
 Volgt uit (*) met inductie
 Zo kan je ook Mergesort analyseren
19
Quicksort voor optimisten (niet
noodzakelijk aartsoptimisten)
 Stel nu dat we altijd verdelingen hebben die
de array splitsen in twee stukken die
verhouding 9 – 1 hebben
 9/10e is gewoon een voorbeeld
 T(n) = T(9n / 10)+ T(n / 10) + Ο(n)
 Recursieboom heeft log10/9 n = Ο(lg n)
lagen
 Per laag Ο(n) dus in zo’n geval eveneens
Ο(n lg n)
 Maar … hoe vaak gebeurt dat?
20
Hoe vaak doen we een goede splitsing?
 In 80% van de gevallen splitsen we 9-1 of
beter…
 Ingewikkelde analyse geeft Ο(n lg n) tijd
gemiddeld over alle mogelijke permutaties
van input als alle getallen verschillend zijn
(doen we niet)
21
Drie
RANDOMIZED QUICKSORT
22
Datastructuren
Hoe zorgen we ervoor dat we heel vaak
goed splitsen
 Idee 1: maak eerst een random permutatie
van de input
 Geeft Ο(n lg n)
 Analyse ingewikkeld
 Idee 2 (beter): gebruik niet A[r] als pivot,
maar gebruik een random element als pivot
 Geeft ook Ο(n lg n)
 Analyse eenvoudiger
 Ietsje sneller
23
Randomized-Partition
Randomized-Partition(A,p,r)
 Kies uniform een random getal i uit de
verzameling {p, p+1, …, r}
 Verwissel A[r] en A[i]
 Partition(A,p,r)
Elk element in A heeft dezelfde kans
om als pivot-element gebruikt te worden
24
Randomized-Quicksort pseudocode
Randomized-Quicksort(A, p, r)
 {Sorteert het deel van de array A[p…r]}
 if p < r
 then
 q = Randomized-Partition(A,p,r)
 Randomized-Quicksort(A, p, q-1)
 Randomized-Quicksort(A, q+1, r)
25
Analyse Randomized Quicksort
 Verschillende manieren om de verwachtte
tijd uit te rekenen
 Netjes: stel recurrente betrekking op, en los
die op (zie o.a. sheets)
 Vandaag: telargument waarbij we kijken
naar “hoe vaak doet een element mee in
een partition”?
26
Maar eerst: slechtste geval
 In het slechtste geval:
 Net als “gewone” Quicksort: gesorteerde rij, en
steeds wordt grootste element als pivot ‘toevallig’
gekozen
 Dus O(n2)
27
Datastructuren
Tijd is O(som partition-lengtes)
 Kijk naar recursieboom
 Totale tijd is O(som van alle lengtes van alle
deelstukken waar we een partitie op doen)
=
 O(som over alle elementen van aantal keren
dat het element in een partitie mee doet)
28
Verwachtte tijd
 Totale verwachtte tijd is O(verwachte som
van alle lengtes van alle deelstukken waar
we een partitie op doen)
=
 O(som over alle elementen van verwachtte
aantal keren dat het element in een partitie
mee doet)
 = n* O(verwachtte aantal keren dat een
element in een partitie meedoet)
29
Afschatten van verwachtte aantal keren
dat een element in een partitie meedoet
 Is O(log n)
 Hoe laten we dit zien?
 Kijk element x, en kijk naar het formaat van
het stuk waar x in zit.
 Begint met formaat n
 Iedere keer een beetje kleiner
 Als formaat 1 is zijn we klaar
 Hoe vaak is het verwachtte aantal keren dat
het kleiner wordt? We laten zien: O(log n)
30
Kansberekening
 Experiment met kans p op succes, 0<p<1
 Wordt r keer uitgevoerd
 Verwachting (E) van aantal successen: pr
 Verwachtte aantal keren tot 1e succes:
1/p
 Verwachtte aantal keren tot re succes: r/p
31
Datastructuren
Kans is ½ dat stuk hooguit ¾ van oude
lengte heeft
 Als we een stuk hebben met r elementen
zijn er r/2 keuzes voor de pivot die zorgen
dat de volgende keer het grootste stuk
hooguit ¾ * r lang is
32
Tellerij klaar
 Hoe vaak kan je n met ¾ vermenigvuldigen totdat je
onder de 1 bent?
 log4/3 n keer = O(log n)
 Wat is het verwachtte aantal keren dat je een
experiment met kans ½ moet doen totdat je s keer
succes hebt?
 2s
 Dus verwachtte aantal keren dat element in partitie
meedoet is hooguit 2 log4/3 n = O(log n) keer
 Dus: verwachtte tijd Quicksort O(n log n)
 Andere analyse (wel in sheets, niet vandaag):
 2n ln n
33
Analyse Randomized-Partition
Slaan we dit jaar over
 Slechtste geval: weer Ο(n2)
 T(n) = max0≤ q≤ n-1 T(q)+T(n-q-1)+Ο(n)
 Verwachtte tijd: analyse doen we hier
aannemend dat alle elementen verschillend
zijn (anders klopt ‘t ook, overigens)
 We doen de analyse hier met behulp van de
sommatiefactormethode
 Eerst: vergelijking looptijd en aantal
vergelijkingen
34
Looptijd vs aantal vergelijkingen
 Stel Quicksort doet X vergelijkingen. Dan gebruikt
het O(n+X) tijd
 Partition doet altijd minstens 1 vergelijking
• Want we roepen Partition alleen aan op stukken met
minstens 2 elementen
 Partition doet O(aantal vergelijkingen in partition) werk
 …
 We gaan nu het verwachtte aantal vergelijkingen
tellen dat Quicksort doet op een array met n
verschillende elementen. Noem dit getal C(n)
35
Technisch detail
 We volgen de analyse uit Concrete
Mathematics. Die gebruikt twee
vergelijkingen per recursieve aanroep extra.
 Deze waardes noemen we D(n).
 D(0)=C(0)=0; als n>0 dan is D(n)>C(n)
 Als we dus voor D(n) een bovengrens
hebben, geeft dat ook een bovengrens voor
C(n)
 Uiteindelijke waarde is dus iets beter (scheelt niet
veel)
36
Aantal vergelijkingen (Randomized)Partition
Partition(A,p,r)
 pivot = A[r];
 i = p – 1;
 for j = p to r – 1 do
 {*}
 if A[j] ≤ pivot
 then
• i ++;
• Verwissel A[i] en A[j]
 Verwissel A[i+1] en
A[r];
 return i+1;
37
 n-1 vergelijkingen op
een array met n
elementen
 Concrete Mathematics
neemt hier n+1
vergelijkingen
Analyse D(n) (1)
 D(0) = 0
 D(1) = 2
 D(n) = n+1 + ????
 Elk van de splitsingen heeft dezelfde kans:
•
•
•
•
•
•
38
0,1,n-1
1,1,n-2
2,1,n-3
…
n-2, 1, 1
n-1, 1, 0
Analyse D(n) (2)
 D(0)= 0
 D(1)= 2
 D(n) = n+1 + 1/n*Σk=0n-1 D(k) + 1/n*Σk=0n-1 D(n-k-
1)
 Elk van de splitsingen heeft dezelfde kans:
•
•
•
•
•
•
0,1,n-1
1,1,n-2
2,1,n-3
…
n-2, 1, 1
n-1, 1, 0
 Of: D(n) = n+1 + (2/n)*Σk=0n-1 D(k) voor n>0
39
2 n −1
D ( n) = n + 1 + ∑ D ( k )
n k =0
n −1
nD(n) = n + n + 2∑ D(k )
2
k =0
Deze hadden we
Maal n nemen
Zelfde vergl. voor n-1
n−2
(n − 1) D(n − 1) = (n − 1) + (n − 1) + 2∑ D(k )
2
k =0
-
nD(n) − (n − 1) D(n − 1) = 2n + 2 D(n − 1)
Vergelijkingen aftrekken
nD(n) = (n + 1) D(n − 1) + 2n
Na vereenvoudigen
40
Stelsel vergelijkingen
 D(0)=0
 nD(n) = (n+1)D(n-1)+ 2n
 Dit stelsel kunnen we met sommatiefactormethode
oplossen
 Idee is: vermenigvuldig formule met sommatiefactor sn
waarbij
• sn = (an-1an-2…a1)/(bnbn-1…b2)
als anD(n)=bnD(n-1)+cn
• Want dan is snbn=sn-1an-1
• En dan krijg je voor E(n)=snanD(n) de formule
E(n)=E(n-1)+sncn
• Wat een somformule voor E en daarna voor D geeft…
41
D(0)=0
nD(n) = (n+1)D(n-1)+ 2n
: dit hadden we
an = n
bn = n+1
cn = 2n
Definitie toepassen:
Alles
maal sn:
(n − 1) ⋅ (n − 2) ⋅  ⋅1
2
=
(n + 1) ⋅ n ⋅  ⋅ 3
(n + 1)n
2
2
2
nD(n) =
2n
(n + 1) D(n − 1) +
(n + 1)n
(n + 1)n
(n + 1)n
Def.:
(*) en (**)
geven:
42
sn =
2
2 D ( n)
E ( n) = sn an D ( n) =
∗ n ∗ D ( n) =
(n + 1)n
n +1
4
E (n) = E (n − 1) +
n +1
(*)
(**)
4
E (n) = E (n − 1) +
n +1
n
dus
4
E ( n) = ∑
k =1 k + 1
We hadden
Want E(0)=0
2 D ( n)
E ( n) =
n +1
n
dus
43
1
D(n) = 2(n + 1)∑
k =1 k + 1
Aantal vergelijkingen randomized
quicksort
n
1
H n = ∑ ≈ ln n
k =1 k
n
1
D(n) = 2(n + 1)∑
k =1 k + 1
Randomized-Quicksort doet verwacht
ongeveer 2(n+1)ln n vergelijkingen
44
Nieuw onderzoek
 Recent werk: quicksort met meer dan 1
pivotelement ... Is soms nèt iets sneller
 “Dual Pivot Quicksort”
45
Datastructuren
ADT versus Datastructuur
 Datastructuur
 is een systematische manier van organiseren van data
en toegang verlenen tot diezelfde data.
 Abstract data type
 is een model van een datastructuur waarin
gespecificeerd is:
• type van de data
• operaties ter ondersteuning van de datastructuur
• de types van de parameters van deze operaties
 Een abstract data type concentreert zich op functionaliteit,
niet op tijd.
 Vandaag: Heap (is ADT), Array-implementatie van Heap
46
Datastructuren
Heap
 “Hoop”, zoals in “een steenhoop”
 Datastructuur, gebruikt voor sorteren en
priority queue
 Een heap is eigenlijk een boom, maar kan
heel efficient in een array worden
weergegeven
 Datastructuren voor “echte” bomen komen
later
47
Heap
 “Bijna volledige binaire boom”
 Vervult de “heap-eigenschap”
 Wat bedoelen we hiermee?
48
Binaire boom
 Binaire boom:
 Iedere knoop heeft 0,
1 of 2 kinderen
 Volledige binaire boom:
 Behalve op het
onderste niveau heeft
elke knoop 2 kinderen
 Een knoop kan hebben:
 Ouder (PARENT)
 Linkerkind (LEFT)
 Rechterkind (RIGHT)
49
Bijna volledige binaire boom
 Alle niveau’s helemaal
gevuld, behalve ‘t
onderste dat een eindje
van links af gevuld is,
en daarna niet meer
 Volledige bb mag ook
50
Twee termen
 Diepte van knoop: afstand naar wortel
 Hoogte van knoop x: maximale afstand
naar blad onder x
51
Heap-eigenschap
 Elke knoop x in de heap heeft een waarde
A[x]
 Max-heap eigenschap: voor alle knopen i
(behalve natuurlijk de wortel van de boom)
geldt: A[PARENT(i)] ≥ A[i]
 Min-heap eigenschap: voor alle knopen i
(behalve natuurlijk de wortel van de boom)
geldt: A[PARENT(i)] ≤ A[i]
52
16
10
14
8
2
4
7
9
3
1
Max-heap
53
Heapsort
 Gebruikt de Heap datastructuur met
implementatie in array
 Heap
54
Implementatie van een heap
16 1
10 3
14 2
4 8
8 2
7 5
6 9
3 7
4 1
10
9
16 14 10 8 7 9 3 2 4 1
55
Implementatie van een heap
 Gebruik een array
 A[1] is de wortel
 A[2], A[3] de
achteenvolgende
elementen op hoogte 1
 A[4], A[5], A[6], A[7]
voor hoogte 2,
 A[2r], … A[2r+1-1] voor
hoogte r
56
 PARENT(i)
 Return  i/2  ;
 LEFT(i)
 Return 2i;
 RIGHT(i)
 Return 2i+1;
Array implementatie
16 1
10 3
14 2
4 8
8 2
7 5
6 9
3
4 1
10
9
16 14 10 8 7 9 3 2 4 1
57
7
 PARENT(i)
 Return  i/2  ;
 LEFT(i)
 Return 2i;
 RIGHT(i)
 Return 2i+1;
“Operaties” op Max-Heap
 Build-Max-Heap
 Maak een heap van een ongeordende array elementen
 Max-Heap-Insert
 Voeg een nieuw element toe aan een heap
 Heap-Extract-Max
 Haal het grootste element uit de heap en lever dat op
 Heap-Increase-Key
 Verhoog de waarde van een element
 Heap-Maximum
 Lever de waarde van het grootste element op (zonder
iets te veranderen)
 NB: Notatie boek is wat slordig (verwart ADT en
implementatie, maar ik volg ‘m toch)
58
Min-heaps
 Net als Max-heaps met min en max (etc.)
omgedraaid
59
Als we deze operaties geimplementeerd
hebben, kunnen we sorteren
 Build-Max-Heap(A)
 For i=0 to n-1 do
 B[n-i] = Heap-Extract-Max(A)
60
Belangrijke subroutine: Max-Heapify
 Max-heapify(A,i)
 {Input-aanname: de binaire boom met
wortel LEFT(i) en de binaire boom met
wortel RIGHT(i) zijn max-heaps}
 {Output: permutatie, zodat de binaire boom
met wortel i is een max-heap}
61
16 1
10 3
4 2
4 8
8 2
7 5
6 9
3
7
5 1
10
9
Idee: als i groter (≥) is dan beide
kinderen: OK, klaar
Anders, verwissel met grootste kind
en ga dan corrigeren op de plek van ‘t
grootste kind
62
16 1
10 3
4 2
4 8
8 2
5
7 5
1
6 9
3
7
16 1
10
10 3
8 2
4 4
8 2
63
5
7 5
1
10
6 9
3
7
Max-heapify
Max-Heapify(A,i)
 links = LEFT(i)
 rechts = RIGHT(i)
 if (links ≤ heap-size[A] and A[links] > A[i])
 then grootste = links
 else grootste = i
 if (rechts ≤ heap-size[A] and A[rechts] >
A[grootste])
 then grootste = rechts
 if (grootste ≠ i)
 then
 Verwissel A[i] en A[grootste]
 Max-Heapify(A,grootste)
64
Analyse Max-Heapify
 Correct?
 Looptijd: O(diepte van i)
 De diepte van een knoop is nooit meer dan
log n, als heap-size(A)=n
 Dus: O(log n)
65
Build-Max-Heap
Build-Max-Heap(A)
 {Input: ongesorteerde rij getallen
A[1…lengte(A)]}
 {Output: A is een permutatie van input die
aan max-heap eigenschap voldoet}
66
Build-Max-Heap
Build-Max-Heap(A)
 {Input: ongesorteerde rij getallen
A[1…lengte(A)]}
 {Output: A is een permutatie van input die
aan max-heap eigenschap voldoet}
 heap-size[A] = lengte(A);
 for i=  lengte(A)/2  downto 1 do
 Max-Heapify(A,i)
That’s all en
‘t klopt ook nog!
67
Correctheid Build-Max-Heap
 Invariant: aan het begin
van de for-loop is elke
knoop i+1, … n de wortel
van een max-heap
 Initieel: klopt, want
boompjes van 1 knoop
 Onderweg: vanwege MaxHeapify… (bespreken
details)
 Terminatie: leuk, want
i=0, dus knoop 1 is wortel
van max-heap, dus hele
array is max-heap
68
for i=  lengte(A)/2 
downto 1 do
Max-Heapify(A,i)
Tijdsanalyse Build-Max-Heap
 Eenvoudige analyse geeft O(n log n)
 Voor iedere i tussen 1 en n/2 doen we O(log n)
werk
 Meer precieze analyse geeft O(n)
 Werk voor knoop i is O(hoogte(i))
 De hoogte van de boom is  log n  (basis 2)
 Er zijn n / 2h+1 knopen met hoogte h in de boom
 Gebruik dat
∞
h
=2
∑
h
h =0 2
Details op bord
69
Heapsort
 Build-Max-Heap(A)
 for i = lengte(A) downto 2 do
 {A[1] is het maximum}
 {A[1…heap-size[A]} is een heap, de elementen
na heap-size[A] zijn gesorteerd maar niet langer
in de heap}
 {Invariant: i = heapsize[A]}
 Verwissel A[1] en A[i];
 Heapsize[A] --;
 Max-Heapify[A];
70
Analyse
 Correct, want …
 O(n log n) tijd want…
71
Next:
 Andere operaties op heaps
 ...
72

Download Report