Rendezési algoritmusok belső rendezés külső rendezés belső rendezési algoritmusok • buborékrendezés (Bubble sort) • kiválasztó rendezés (Selection sort) • számláló rendezés (Counting sort) • beszúró rendezés (Insertion sort) • Shell-rendezés (Shell sort) • összefésülő rendezés (Merge sort) • kupacrendezés (Heapsort) • gyorsrendezés (Quicksort) • edényrendezés (Bucket sort) • számjegyes rendezés (Radix sort)
1
Buborékrendezés (Bubble sort) Buborékrendezés-1(A) 1. 2. 3. 4. 5. 6. 7. 8. 9.
n := hossz[A] repeat ind := 0 for i := 1 to n − 1 do if Ai > Ai+1 then Ai ⇔ Ai+1 ind := 1 until ind = 0 return A
repeat . . . until ind = 0 helyett C-ben: do. . . while ind ! = 0 Legrosszabb esetben az összehasonlítások száma: (n − 1) + (n − 2) + . . . + 1 =
2
(n − 1)n = Θ(n2). 2
Buborékrendezés-2(A) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
ind := hossz[A] repeat k := ind − 1 ind := 0 for i := 1 to k do if Ai > Ai+1 then Ai ⇔ Ai+1 ind := i until ind = 0 return A
Legrosszabb esetben az összehasonlítások száma szintén: (n − 1)n = Θ(n2). (n − 1) + (n − 2) + . . . + 1 = 2 Átlagérték: ∼
n2 4
= Θ(n2)
Példa
3
Kiválasztó rendezés (Selection sort) Kiválasztjuk a legkisebb elemet, és az első helyre tesszük, majd úgyanígy folytatjuk a maradék sorozattal. Kiválasztó-rendezés(A) 1. n := hossz[A] 2. for i := 1 to n − 1 3. do min := i 4. for j := i + 1 to n 5. do if Amin > Aj 6. then min := j 7. Ai ⇔ Amin 10. return A
Bonyolultság szintén Θ(n2). Példa
4
Számláló rendezés (Counting sort) Különböző elemek esetében minden elemre megszámoljuk a kisebb elemeket. Ha k − 1 kisebb egy elemnél, akkor ő a k-adik helyre kerül. Számláló-rendezés-1(A) 1. n := hossz[A] 2. for i := 1 to n 3. do k := 1 4. for j := 1 to n 5. do if Ai > Aj 6. then k := k + 1 7. Bk := Ai 8. return B
Bonyolultság szintén Θ(n2). Ha az elemek 0 és n közötti egész számok, akkor meg lehet valósítani Θ(n) időben.
5
Ha az elemek nem mind különbözőek, akkor helyet keresünk az illető elemnek. Számláló-rendezés-2(A) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
n := hossz[A] for i := 1 to n do Bi := 0 for i := 1 to n do k := 1 for j := 1 to n do if Ai > Aj then k := k + 1 while Bk 6= 0 do k := k + 1 Bk := Ai return B
Bonyolultság szintén Θ(n2).
6
Beszúró rendezés (Insertion sort) Beszúró-rendezés(A) 1. n := hossz[A] 2. for i := 2 to n 3. do k := Ai 4. j := i − 1 5. while (j > 0) és (Aj > k) 6. do Aj+1 := Aj 7. j := j − 1 8. Aj+1 := k 9. return A
Bonyolultság legrosszabb esetben szintén Θ(n2). Példa
7
Shell-rendezés (Shell sort) ht > ht−1 > . . . > h2 > h1 = 1 növekmények Shell-rendezés(A, h) 1. 2. 3. 4. 5. 6. 7. 7. 8. 9. 10. 11.
n := hossz[A] t := hossz[h] for s := t downto 1 do h := hs for i := h + 1 to n do k := Ai j := i − h while (j > 0) és (Aj > k) do Aj+h := Aj i := i − h Aj+h := k return A
Bonyolultság legrosszabb esetben Θ(n2), átlagesetben sokkal jobb. Példa
8
Összefésülő rendezés (Merge sort) Neumann János, 1945 Mergesort(A, b, j) b bal index, j jobb index
1. if b < j
2. 3. 4. 5. 7.
b+j 2 Mergesort(A, b, k) Mergesort(A, k + 1, j) Összefésül(A, b, k, j) return A then k :=
9
Összefésül(A, b, k, j) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
n1 := k − b + 1 n2 := j − k for p := 1 to n1 do Lp := Ab+p−1 for r := 1 to n2 do Rr := Ak+r Ln1+1 := ∞ Rn2+1 := ∞ p := 1 r := 1 for i := b to j do if Lp ≤ Rr then Ai := Lp p := p + 1 else Ai := Rr r := r + 1
strázsa strázsa
Az eljárás hívása: Mergesort(A, 1, n), ha A = (A1, A2, . . . , An). Bonyolultság: Θ(n log n). Példa 10
Kupacrendezés (Heapsort) Kupacot használunk és a Kupacot_épít valamint a Kupacol eljárást. A bemeneti A1, A2, . . . , An sorozatra meghívjuk a Kupacot_épít eljárást, amely kupactulajdonságúvá változtatja a kupacot. Kupacol(A, i) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
b := Bal(i) j := Jobb(i) if (b ≤ kupacm´ eret[A]) és (Ab > Ai) then max := b else max := i if (j ≤ kupacm´ eret[A]) és (Aj > Amax) then max := j if max 6= i then Ai ⇔ Amax Kupacol(A, max)
Kupacot-épít(A) 1. kupacm´ eret[A] := hossz[A] hossz[A] downto 1 2. for i := 2 3. do Kupacol(A, i) 11
A kupacrenzedés a gyökérelemet (amely a legnagyobb) az utolsó helyre teszi (felcseréléssel), kiveszi azt a kupacból, a többi elemre helyreállítja a kupactulajdonságot, és ugyanúgy folytatja. Kupacrendezés(A) 0. 1. 2. 3. 4. 5. 6.
Kupacot-épít(A) eret[A] := hossz[A] kupacm´ for i := n downto 2 do A1 ⇔ Ai kupacm´ eret[A] := kupacm´ eret[A] − 1 Kupacol(A,1) return A
Bonyolultság: Θ(n log n). Példa
12
Gyorsrendezés (Quicksort) Gyorsrendezés(A, b, j) 1. if b < j 2. then k := Feloszt(A, b, j) 3. Gyorsrendezés(A, b, k − 1) 4. Gyorsrendezés(A, k + 1, j) 5. else return A Feloszt(A, b, j) 1. 2. 3. 4. 5. 6. 7. 8.
x := Aj i := b − 1 for k := b to j − 1 do if Ak ≤ x then i := i + 1 Ai ⇔ Ak Ai+1 ⇔ Aj return i + 1
Az eljárás hívása: Gyorsrendezés(A, 1, n)
13
14
C. A. Hoare felosztó algoritmusa: Feloszt2(A, b, j) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
x := Ab i := b − 1 j := j + 1 while igaz repeat j := j − 1 until Aj ≤ x repeat i := i + 1 until Ai ≥ x if i < j then Ai ⇔ Aj else return j
15
Nem rekurzív változat Az Ab, . . . , Aj résztömbök indexeit egy veremben őrizzük [b, j] formában, kezdetben a verem üres. push([b, j]) beteszük a verembe, pop([b, j]) kiveszzük a veremből Nemrekurzív-Gyorsrendezés(A) 1. 2. 3. 4. 5. 6. 7. 8. 9.
n := hossz[A] push([1, n]) while a verem nem üres do pop([b, j]) while b < j do k := Feloszt(A, b, j) push([k + 1, j]) j := k − 1 return A
Példa Bonyolultság legrosszabb esetben: Θ(n2), átlagesetben Θ(n log n).
16
Edényrendezés (Bucket sort) Az elemeket egyenletes elosztásúaknak tekintjük. Lineáris bonyolultságú. Példa
17
Számjegyes rendezés (Radix sort) A legkisebb helyértékű számjeggyel kezdjük a csoportosítást, majd haladunk balra. Lineáris bonyolultságú. Példa 40325
50231
50231 | {z } 1
38123 | {z } 3
40325 |
37005 {z 5
42025}
37005 | {z }
38123 |
40325 {z 2
42025}
50231 | {z }
37005 | {z 42025} 0
38123 | {z } 1
50231 | {z } 2
40325 | {z }
50231 | {z 40325}
42025 | {z }
37005 | {z }
38123 | {z }
37005 | {z 38123}
42025 | {z 40325}
50231 | {z }
0
0
3
37005
38123
2
7
4
18
42025
3
3
8
5
algoritmus átlag legrosszabb buborékrendezés (Bubble sort) Θ(n2) Θ(n2) kiválasztó rendezés (Selection sort) Θ(n2) Θ(n2) számláló rendezés (Counting sort) Θ(n2) Θ(n2) beszúró rendezés (Insertion sort) Θ(n2) Θ(n2) Shell-rendezés (Shell sort) Θ(n2) gyorsrendezés (Quicksort) Θ(n log n) Θ(n2) összefésülő rendezés (Merge sort) Θ(n log n) Θ(n log n) kupacrendezés (Heapsort) Θ(n log n) Θ(n log n)
19
Topologikus rendezés mélységi bejárás alkalmazása
20
21
Külső rendezés (Knuth, 3. kötet) két lépésből áll: futamok előállítása (angolul run) futamok összefésülése két módszer: 1) többfázisú öszefésülés 2) kaszkád összefésülés Többfázisú öszefésülés 3 szalagot használunk: T1, T2, T3 1. Osszuk szét a kezdeti futamokat felváltva T1-en és T2-n. 2. A T1 és T2 szalagokról fésüljük össze a futamokat T3-ra. Ha T3 egyetlen futamot tartalmaz, álljunk meg. 3. Másoljuk a T3-on levő futamokat felváltva T1-re és T2-re, majd folytassuk a 2. lépéssel 1. fázis 18 15 − 2. fázis 13 − 25 3. fázis − 33 22 4. fázis 52 31 − 5. fázis 51 − 81 6. fázis − 131 − k n jelentése: n darab k hosszúságú futam (k hosszúság: az eredeti futam k-szorosa) 22
Kaszkád összefésülés
23
http://www.youtube.com/watch?v=Ns4TPTC8whw http://www.youtube.com/watch?v=ROalU379l3U http://www.youtube.com/watch?v=CmPA7zE8mx0 http://www.youtube.com/watch?v=lyZQPjUT5B4 http://www.youtube.com/watch?v=XaqR3G_NVoo
24
