10. Előadás
Beszúró rendezés Használjuk a kupacokat rendezésre! Szúrd be az elemeket egy kupacba! Amíg a sor ki nem ürül, vedd ki a kupacból a
maximális elemet, és tedd az eredmény (rendezett) sorba!
2
Kupacrendezés Az s sorban lévő elemeket rendezzük a
k kupac segítségével! k.empty not s.isempty
e:=s.out k.insert(e) not k.isempty e:=k.delmax s.in(e) 3
Kupacrendezés A kupacok hatékony rendezőt adnak: Szúrjunk be minden elemet a kupacba n elem, ezekhez kell O(log2n) O(n log n) sorrendben távolítsuk el az elemeket n elem, ezekhez kell O(log2n) O(n log n) Összesen O(n log n)
ignorálva a 2-es konstanst, stb. Nézzünk meg egy animációt a kupacrendezésre!
4
Gyorsrendezés (Quicksort) hatékony rendezési algoritmus C.A.R. Hoare készítette, 1960. Az „Oszd meg és Uralkodj” algoritmus egy példája Két fázis Partíciós fázis
Oszd a munkát két részre!
Rendezési fázis
Uralkodj a részeken!
Gyorsrendezés (Quicksort) Partíció Válassz egy „strázsát” (pivot)! Válaszd a strázsa pozícióját olyanra, hogy
minden elem tőle jobbra nagyobb legyen! minden elem tőle balra kisebb legyen!
< strázsa
strázsa
> strázsa
Gyorsrendezés (Quicksort) Uralkodj Alkalmazd ugyanezt az algoritmust mindkét félre!
< strázsa < p’
p’
> p’
> strázsa strázsa
< p”
p”
> p”
Gyorsrendezés (Quicksort) Implementáció quicksort( void *a, int also, int felso ) { int pivot; /* Terminálási feltétel! */ if ( felso > also ) Oszd meg { pivot = feloszt( a, also, felso ); quicksort( a, also, pivot-1 ); quicksort( a, pivot+1, felso ); Uralkodj } }
Quicksort - Megosztás Ez a példa int-eket használ az egyszerűség kedvéért! Bármelyik elem jó strázsának, válaszd a bal szélsőt!
23 12 15 38 42 18 36 29 27
also
felso
Quicksort - Megosztás állítsd be a bal és jobb végét
bal
jobb
23 12 15 38 42 18 36 29 27
also
str_elem: 23
felso
Quicksort - Megosztás mozgasd a jelzéseket, míg szembetalálkoznak!
bal
jobb
23 12 15 38 42 18 36 29 27
also
str_elem: 23
felso
Quicksort - Megosztás mozgasd a bal jelzőt, míg a str_elem-nél elemekre mutat!
bal
mozgasd a jobb jelzőt hasonlóan
jobb
23 12 15 38 42 18 36 29 27
also
str_elem: 23
felso
Quicksort - Megosztás Cseréld ki a str_elem két oldalán rossz sorrendben lévő elemeket!
bal
jobb
23 12 15 38 42 18 36 29 27
also
str_elem: 23
felso
Quicksort - Megosztás A „bal” és a „jobb” szembetalálkoztak, így állj le!
bal
jobb
23 12 15 18 42 38 36 29 27
also
str_elem: 23
felso
Quicksort - Megosztás Végül cseréld ki a „str_elem”-et és a „bal”-nál lévőt
bal
jobb
23 12 15 18 42 38 36 29 27
also
str_elem: 23
felso
Quicksort - Megosztás add vissza az „str_elem” pozícióját! bal 18 12 15 23 42 38 36 29 27
also
str_elem: 23
felso
Quicksort – Uralkodj!
rekurzívan rendezi a bal felét
rekurzívan rendezi a jobb felét
18 12 15 23 42 38 36 29 27 str_elem: 23
Gyorsrendezés algoritmusa Gyorsrendezés (A, also, felso) also < felso q := Feloszt(A, also, felso) Gyorsrendezés (A, also, q-1) Gyorsrendezés (A, q+1, felso)
SKIP
(A vektorban, also és felso indexek között)
Feloszt(A, also, felso)
str_elem:=A[also]; bal:=also; jobb:=felso;
bal < jobb A[bal]<= str_elem and bal
= str_elem and jobb >also jobb:= jobb-1 bal < jobb Csere(A[bal], A[jobb])
SKIP
A[also]:=A[bal]; A[bal]:= str_elem; return bal;
Quicksort - Analízis Felosztás vizsgálj meg minden elemet egyszer O(n) Uralkodás az adatok kétfelé osztása O(log2n) összesen szorzat O(n log n) ugyanaz, mint a Heapsort a quicksort általában gyorsabb
kevesebb összehasonlítás
De van egy gond …
Quicksort – az igazság! Mi történik, ha az adatok már rendezettek, vagy
majdnem rendezettek? Azt várnánk, hogy akkor gyorsabb lesz!
Quicksort – az igazság! Rendezett adatok
pivot ? < pivot
1 2 3 4 5 6 7 8 9
> pivot
Quicksort – az igazság! Rendezett adatok Minden partíció létrehoz egy 0 méretű feladatot és egy n-1 méretűt! A partíciók száma?
pivot 1 2 3 4 5 6 7 8 9 pivot
> pivot
2 3 4 5 6 7 8 9 > pivot
Quicksort – az igazság! pivot Rendezett adatok Minden partíció létrehoz 1 2 3 4 5 6 7 8 9 egy 0 méretű feladatot > pivot és egy n-1 méretűt! pivot A partíciók száma? 2 3 4 5 6 7 8 9 minden n időigénye O(n) összesen n O(n) > pivot vagyis O(n2) A Quicksort olyan rossz, mint a buborék vagy a
beszúrásos rendezés?
Quicksort – az igazság! A Quicksort O(n log n) viselkedése a majdnem egyforma partíciókon múlik O( log n ) van
Átlagosan is majdnem ez a helyzet és a Quicksort általában O(n log n) Mit lehet tenni? Általában semmit De javíthatjuk az esélyeinket!
Quicksort – A pivot választása Bármelyik strázsa megteszi… Válasszunk egy másikat … pivot 1 2 3 4 5 6 7 8 9 < pivot
> pivot
amikor a partíciók egyformák akkor O(n log n) időre lesz szükség
Quicksort – 3-ból a középső pivot Végy 3 pozíciót, és válaszd a középsőt Pl. első, középső, utolsó
1 2 3 4 5 6 7 8 9 a középső 5 ez a rendezett adatok legjobb felosztása! O(n log n) idő
Mivel a rendezett (vagy majdnem rendezett) adatok elég
gyakoriak, ez egy jó stratégia különösen, ha azt várjuk, hogy az adataink rendezettek
lesznek!
Quicksort – Véletlen pivot Válassz egy strázsát véletlenszerűen Minden felosztásnál másik pozíciót Átlagosan a rendezett adatokat jól osztja szét O(n log n) idő
Kulcs követelmény: A pivot kiválasztása O(1) idő kell legyen
Quicksort - Garantált O(n log n)? Soha! A tetszőleges pivot választási stratégia vezethet O(n2) időhöz Itt a 3-ból a középső
kiválasztja a 2-t egy partícióba 1 elem kerül,
1 4 9 6 2 5 7 8 3
a másikba 7
következőnek kiválasztja a 4-t 1 2 4 9 6 5 7 8 3 egy partícióba 1 elem kerül, a másikba 5
Rendezés Buborék, Beszúrásos, Maximumkiválasztásos O(n2) rendezések egyszerű kód kis n-re gyors lehet (rendszer függő)
Quick Sort Oszd meg és uralkodj O(n log n)
Quicksort O(n log n)
de …. Lehet O(n2) is A pivot kiválasztásától függ 3-ból a középső véletlen pivot Jobb, de nem garantált
Quicksort használjuk inkább a Heapsort-ot? A Quicksort általában gyorsabb kevesebb összehasonlítás és csere néhány empirikus adat: Quick
Heap
Hasonl Csere
100 200 500
712 1682 5102
148 328 919
Beszúró
Hasonl
Csere
Hasonl
Csere
2842 9736 53113
581 9736 4042
2596 10307 62746
899 3503 21083
Quicksort Heap Sort Quicksort általában gyorsabb néha O(n2)
jobb pivot választás csökkenti a valószínűségét ha átlagosan jó végrehajtási időt akarunk, használjuk ezt üzleti alkalmazások, információs rendszerek
Heap Sort általában lassúbb Garantált O(n log n) … lehet rá építeni, ezt a tervezésben felhasználni! használjuk például real-time rendszerekhez
Az idő egy megszorítás
