1 Algorytmy i Struktury Danych SortowanieWykład 4 Prowadzący: dr Paweł Drozda
2 Treść wykładu Problem sortowania Sortowanieprzez wstawianie (Insertion sort) bąbelkowe (Bubble sort) przez wybór (Selection sort) przez scalanie (Merge sort) szybkie (Quick sort) Przez kopcowanie Przez zliczanie (CountingSort) Pozycyjne (Radix sort)
3 Opis problemu Ciąg elementów e={e1,...,en} należących do liniowo uporządkowanej przestrzeni < E,≤ > Permutacja i1,...,in liczb 1,...,n taka, że ei1 ≤... ≤ ein 6, 3, 2, 7, 4, 1, 5 6, 3, 7, 2, 4, 1, 5
4 Sortowanie przez wstawianieAlgorytm sortowania InsertionSort(A) for j:=2 to length(A) begin key:=A[j] /* Wstaw A[j] w posortowany ciąg A[1..j-1].*/ i:= j-1 while i>0 i A[i] > key do A[i+1] := A[i] i:= i-1 end A[i+1] := key Przykład działania algorytmu
5 Sortowanie przez wstawianieSortowanie w miejscu Czas działania algorytmu niech n = length(A) pętla for: n-1 razy pętla while: optymistycznie: 1 przesunięcie pesymistycznie: n-1 przesunięć średnio: (n-1)/2 przesunięć Złożoność: O(n2) sortowanie przyrostowe
6 Sortowania bąbelkowe Algorytm sortowania BubbleSort(A) for i:=1 to n-1n:=length(A) for i:=1 to n-1 begin for j:=n downto i+1 if A[j]
7 Sortowania bąbelkowe Sortowanie w miejscu, przyrostoweCzas działania algorytmu pętla for i: n-1 razy pętla for j: średnio n/2 razy (nawet jeżeli warunek nie jest spełniony) Złożoność: O(n2) Najgorszy przypadek: ciąg posortowany odwrotnie
8 Sortowania bąbelkowe Usprawnienia:zmiana kierunku „bąbelków” – Shake sort / Coctail sort Sortowanie grzebieniowe (Comb sort) rozpiętość = n/1.3 (wyznaczone empirycznie) sortuj kolejno wszystkie pary obiektów odległych o rozpiętość podziel rozpiętość przez 1.3 i wykonuj ponownie powyższe sortowanie do czasu, gdy rozpiętość osiągnie wartość 1 Złożoność: prawdopodobnie O(nlogn)
9 Combsort– Przykład Gap=6 2 4 6 8 7 1 3 Gap=4 1 4 3 8 7 2 6 Gap=3 4 2 17 1 3 Gap=4 1 4 3 8 7 2 6 Gap=3 4 2 1 7 3 8 6 Gap=2 4 1 2 7 3 8 6 Gap=1 1 4 2 3 7 6 8 Gap=1 1 2 4 3 6 7 8 Gap=1 1 2 4 3 6 7 8 dr Paweł Drozda
10 Sortowanie przez wybórAlgorytm sortowania SelectionSort(A) n:=length(A) for i:=1 to n-1 begin wybierz najmniejszy element spośród A[i]...A[n] i zamień go miejscami z A[i] end
11 Sortowanie przez wybórSortowanie w miejscu, przyrostowe Czas działania algorytmu pętla for: n-1 razy wyszukanie najmniejszego elementu: od 1 do n razy, średnio n/2 porównań Złożoność: O(n2)
12 Sortowanie przez scalaniePodziel A w połowie na 2 podciągi Kontynuuj dzielenie rekurencyjnie Jeżeli podciągów nie da się już podzielić, scal je sortując Nieposortowany ciąg Pojedyncze elementy Podział Posortowany ciąg Scalanie
13 Sortowanie przez scalanieAlgorytm sortowania MergeSort(lo, hi) if lo=hi zakończ m := (lo+hi)/2 MergeSort(lo,m) MergeSort(m+1,hi) Merge(lo,m,hi) Merge(lo, med, hi) i := lo, j := med+1 for k:=1...hi-lo+1 begin if A[i]>A[j] begin A’[k] := A[i], i:=i+1 end else begin A’[k] := A[j], j:=j+1 A[lo]...A[hi] := A’[1]...A[hi-lo+1] Przykład dla:
14 Sortowanie przez scalanieDziel i zwyciężaj bazuje na obserwacjach: łatwiej posortować krótszy ciąg niż dłuższy łatwiej otrzymać posortowany ciąg ze złączenia 2 posortowanych podciągów, niż z 2 nieposortowanych podciągów (Merge) z indukcji matematycznej otrzymujemy złożoność O(nlogn) Wymaga Ω(n) dodatkowej pamięci (Merge)
15 Sortowanie szybkie Wybieramy element dzielący pDzielimy A na 2 podciągi: < p i ≥ p Sortujemy niezależnie (rekurencyjnie) te podciągi Dziel i zwyciężaj
16 Sortowanie szybkie Algorytm sortowania QuickSort(lo, hi)if A[lo]...A[hi] zawiera przynajmniej 2 różne wartości begin p:= większa z 2 różnych wartości przestaw elementy w A tak, że dla pewnego k, lo
17 Sortowanie szybkie 5 5 2 4 6 1 3 2 4 4 1 3 5 6 6 5 4 6 2 3 1 1 2 2 3 4 5 6 1 2 3 3 2 3
18 Sortowanie szybkie sortuje w miejscu Złożonośćprzestawienie elementów – O(n) liczba wywołań rekurencyjnych: średnio: O(log(n)) pesymistycznie O(n) średnia złożoność: O(n log(n)) Najszybszy algorytm sortujący, dobra implementacja będzie 2-3 razy szybsza niż MergeSort
19 Kopiec Inaczej stóg/stertaDrzewo binarne, które zawiera elementy e={e1,...,en} należące do liniowo uporządkowanej przestrzeni < E,≤ > drzewo zrównoważone drzewo uporządkowane węzeł ma własność kopca gdy: własność kopca = własność częściowego uporządkowania drzewo zrównoważone = drzewo doskonałe: wszystkie poziomy drzewa, z wyjątkiem co najwyżej ostatniego poziomu, są maksymalnie zapełnione, a na ostatnim poziomie wszystkie liście są zgrupowane maksymalnie na lewo. WARTOŚĆ(T,RODZIC(T,n)) ≥ WARTOŚĆ(T,n) liście zawsze spełniają własność kopca
20 Kopiec jako tablica wierzchołek wstaw do tab[0]dla i-tego węzła tab[i]: lewe dziecko: tab[2*i+1] prawe dziecko: tab[2*i+2] rodzic: tab[i/2]? 18 15 12 10 9 7 6 4 3 1 blad: ojciec[i/2] 1 2 3 4 5 6 7 8 9 18 15 12 10
21 Z drzewa do kopca Zamiana wartości: jeżeli węzeł nie spełnia własności kopca, to zamień jego wartość z synem o większej wartośći Syn może utracić własność kopca 10 15 18 18 15 10
22 Konstrukcja kopca dodawaj nową wartość do sterty i sprawdź czy nie została zaburzona własność kopca dla rodzica nowo dodanego węzła jeżeli tak, to rekurencyjnie zamieniaj w górę ZamienWGore(n): r = RODZIC(n) if WARTOŚĆ(n) > WARTOŚĆ (r) begin zamień wartości n i r ZamienWGore(r) end
23 Usunięcie korzenia Wierzchołek kopca zawiera największą wartośćNa miejsce korzenia wstaw ostatni węzeł drzewa Rekurencyjnie przywróć własność kopca dla korzenia i jego synów ZamienWDol(n): s = węzeł z większą wartością spośród synów n if WARTOŚĆ(s) > WARTOŚĆ (n) begin zamień wartości n i s ZamienWDol(s) end
24 Sortowanie przez kopcowanieUtwórz kopiec Dla każdego wierzchołka – zaczynając od wierzchołka n/2 do korzenia kopca przywróć własność kopca Usuwaj po kolei elementy które są korzeniami, aż do momentu dekonstrukcji całego kopca dr Paweł Drozda
25 Sortowanie przez kopcowanie - przykład4 5 8 6 7 2 1 4 4 5 8 7 8 6 7 2 1 6 5 2 1 8 7 1 5 4 6 2 7 4 6 1 2 5 2 4 4 4 1 6 5 2 1 1 1 1 5 2 2 1 2 4 5 6 7 8 dr Paweł Drozda
26 Sortowanie przez zliczanieSortowanie bez porównywania elementów Założenie: sortujemy liczby całkowite Idea: ile elementów jest mniejsze od liczby x? 1 2 3 4 5 6 7 8 1 2 3 4 5 6 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 3 4 4 4 6
27 CountingSort: for i=1…k do { C[i]=0; } for i=1…n do { C[A[i]]++; }for i=2…k do { C[i] = C[i]+C[i-1]; } for i=n…1 do { B[C[A[i]]] = A[i]; C[A[i]]--; } O(k) O(n) O(k) Ostatecznie: =O(k)+O(n)+O(k)+O(n) =2(O(k)+O(n)) =2O(k+n)=O(k+n) O(n)
28 Sortowanie pozycyjne Herman Hollerith 1884
29 Radix sort Liczby całkowite liczba składa się z d cyfrcyfra przybiera wartości od 0 do k-1 329 457 657 839 436 720 355 1 2 3 4 5 6 7 8 9
30 Radix sort Sortujemy po kolejnych cyfrach Sortowanie jest stabilneutrzymuje kolejność występowania dla elementów o tym samym kluczu np. sortowanie rekordu z datą: {d,m,r} Złożoność obliczeniowa: d*O(n+k)