Probabilistyczna wersjaRandomized-Partition(A, p, r)
1 i := Random(p, r)
2 zamień A[p] A[i]
3 return Partition(A, p, r)
Randomized-Quicksort(A, p, r)
1 if p < r
2 then q := Randomized-Partition(A, p, r)
3 Randomized-Quicksort(A, p, q)
3 Randomized-Quicksort(A, q+1, r)
Sortowanie: kopce
16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 16 14 10 8 1 2 3 4 5 6 7 8 9 10 8 7 9 3 2 4 1 Parent(i)
return i/2
Left(i)
return 2i
Right(i)
return 2i+1 Własność kopca: dla każdego węzła i, który nie jest korzeniem: A[Parent(i)] A[i]
Przywracanie własności kopca
Zakładamy, że drzewa binarne zaczepione w Left(i) i Right(i) są kopcami, ale A[i] może być mniejszy od swoich synów, przez co narusza własność kopca. Żeby spełniała się własność kopca, stosujemy procedurę Heapify:
Heapify(A, i)
1 l := Left(i) 6 if r heap-size[A] i A[l]> A[i]
2 r := Right(i) 7 then largest := r
3 if l heap-size[A] i A[l]>A[i] 8 if largest i
4 then largest := l 9 then zamień A[i]A[largest]
5 else largest := i 10 Heapify(A, largest)
Przykład działania procedury Heapify
4 1 14 2 7 3 2 4 8 5 1 6 a) 14 1 4 2 7 3 2 4 8 5 1 6 b) 14 1 8 2 7 3 2 4 4 5 1 6 c) Czas działania Heapify - O(lg n) = O(h)
(n - liczba węzłów drzewa, h - wysokość drzewa)
Budowanie kopca Z dowolngo drzewa binarnego można zrobić kopiec w sposób wstępujący (bottom-up)
Build-Heap(A)
1 heap-size[A] := length[A]
2 for i:= length[A]/2 downto 1
3 do Heapify(A, i)
Czas działania Build-Heap - O(n)
Heapsort(A)
1 Build-Heap(A)
2 for i := length[A] downto 2
3 do zamień A[1] A[i]
4 heap-size[A] := heap-size[A]-1
5 Heapify(A, 1).
Czas działania Heapsort: O(n) + (n-1)O(lg n) = O(n lg n).
Quicksort - sortowanie szybkie
Algorytm sortowania szybkiego jest oparty na technice „dziel i zwyciężaj”.
Dziel: Tablica A[p…r] jest dzielona na dwie niepuste podtablice A[p…q] i A[q+1…r] takie, że każdy element A[p…q] jest nie większy niż każdy element A[q+1…r].
Zwyciężaj: Dwie podtablice A[p…q] i A[q+1…r] są sortowane za pomocą rekurencyjnych wywołań algorytmu Quicksort.
Quicksort(A, p, r)
1 if p < r
2 then q := Partition(A, p, r)
3 Quicksort(A, p, q)
4 Quicksort(A, q+1, r)
Dzielenie tablicy
5 3 2 8 6 4 1 3 7 i j 5 3 2 8 6 4 1 3 7 i j 3 3 2 8 6 4 1 5 7 i j 3 3 2 8 6 4 1 5 7 i j 3 3 2 1 4 6 5 7 i j Partition(A, p, r)
1 x := A[p]
2 i := p - 1
3 j := r + 1
4 while True
5 do repeat j := j - 1
6 until A[j] x
7 repeat i := i + 1
8 until A[i] x
9 if i < j
10 then zamień A[i]A[j]
11 else return j
Czas działania Quicksort
n n-1 1 n-2 1 1 2 1 1 n n n n-1 3 2 (n2) Najgorszy przypadek lg n n n/2 n/2 n/4 n/4 n/4 n/4 1 1 1 1 1 1 1 1 n n n n n (n lg n) Najlepszy przypadek Najgorszy przypadek podziałów: (n2)
Najlepszy przypadek podziałów: (n lg n)
Czas działania w średnim przypadku zbliżony jest do najlepszego: (nlgn)
Probabilistyczna wersja
Randomized-Partition(A, p, r)
1 i := Random(p, r)
2 zamień A[p] A[i]
3 return Partition(A, p, r)
Randomized-Quicksort(A, p, r)
1 if p < r
2 then q := Randomized-Partition(A, p, r)
3 Randomized-Quicksort(A, p, q)
3 Randomized-Quicksort(A, q+1, r)
Sortowanie przez zliczanie
3 6 4 1 1 2 3 4 5 6 7 8 3 4 1 4 A 2 0 2 3 1 2 3 4 5 6 0 1 C 2 2 4 7 1 2 3 4 5 6 7 8 C 1 2 3 4 5 6 7 8 4 B 2 2 4 6 1 2 3 4 5 6 7 8 C Counting-Sort(A, B, k)
1 for i := 1 to k
2 do C[i] := 0
3 for j := 1 to length[A]
4 do C[A[i]] := C[A[i]] + 1
5 // C[i] zawiera teraz liczbę elementów równych i
6 for i := 2 to k
7 do C[i] := C[i] + C[i-1]
8 // C[i] zawiera liczbę elementów mniejszych lub równych i
9 for j := length[A] downto 1
10 do B[C[A[i]]] := A[i]
11 C[A[i]] := C[A[i]] - 1
Sortowanie pozycyjne
Radix-Sort(A, d)
1 for i := 1 to d
2 do posortuj przez zliczanie tablicę A według cyfry I
329 720 720 329 Sortowanie przez zliczanie
457 355 329 355 i sortowanie pozycyjne
657 436 436 436 działają w czasie liniowym
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839
Comments