1 ALGORYTMY I STRUKTURY DANYCHWYKŁAD 05 Problem Sortowania Grażyna Mirkowska PJWSTK, semestr zimowy 2002

2 G. Mirkowska, ASD 05 SortowaniePlan wykładu Sformułowanie problemu Sortowanie przez porównywanie elementów Sortowanie przez wstawianie Sortowanie przez selekcję Operacja scalania ciągów uporządkowanych Sortowanie przez scalanie litopad 2002 G. Mirkowska, ASD 05 Sortowanie

3 Sformułowanie problemuDany jest ciąg e elementów e1,e2,... , en należących do pewnej liniowo uporządkowanej przestrzeni . Znaleźć taką permutację i1, i2,... ,in liczb 1,..., n aby ei1ei2 ... ein lub Znaleźć taką funkcję różnowartościową i „na” f : {1,2...,n}  {e1,e2,... , en }, że dla każdego i litopad 2002 G. Mirkowska, ASD 05 Sortowanie

4 Sortowanie przez selekcjęMetoda Sortowanie odbywa się w n-1 przebiegach. W i-tym przebiegu szukamy i-tego najmniejszego elementu. Algorytm { for i := 1 to n-1 do min := i; j := i+1; while j < n+1 do if e[j] < e[min] then min := j fi od; swap(e[i],e[min]); od } Selection_sort min e[i] Odcinek uporządkowany litopad 2002 G. Mirkowska, ASD 05 Sortowanie

5 G. Mirkowska, ASD 05 SortowanieDiagram przepływu i := 1 e[1] ...  e[i-1]  {e[i],...,e[n]} nie i < n tak e[1] ...  e[i-1]  {e[i],...,e[n]} Niezmienik Znajdź x takie, że x = minimum( e[i],..., e[n]) i := i+1 x  {e[i],...,e[n]} Zamień miejscami x i e[i] e[1] ...  e[i-1]  e[i]  {e[i+1],...,e[n]} litopad 2002 G. Mirkowska, ASD 05 Sortowanie

6 G. Mirkowska, ASD 05 SortowanieKoszt algorytmu Twierdzenie Algorytm Selection_sort jest poprawnym rozwiązaniem problemu sortowania. W dowolnej strukturze danych, której elementy są liniowo uporządkowane przez relację  , algorytm zatrzymuje się dla dowolnych danych i daje w wyniku ciąg uporządkowany niemalejąco. A. Jeśli operacją dominującą jest porównywanie elementów: Koszt algorytmu T(n) = n n = n(n-1)/2 = (n2) B. Jeśli operacją dominującą jest zamiana elementów T(n) = 1*(n-1) = n-1 = (n) litopad 2002 G. Mirkowska, ASD 05 Sortowanie

7 Sortowanie przez wstawianieSortowanie odbywa się w n -1 przebiegach. W i-tym przebiegu elementy na pozycjach 1...(i-1) są już uporządkowane, a wstawiamy i-ty element przepychając go do przodu na właściwe miejsce, tak by stworzył wraz z innymi ciąg uporządkowany długości i. Metoda 4 8 5 Przykład 3 Odcinek uporządkowany i-ty element X 9 6 itd litopad 2002 G. Mirkowska, ASD 05 Sortowanie

8 G. Mirkowska, ASD 05 SortowanieSchemat algorytmu start Niezmiennik i := 2 e[1]...  e[i-1] , i < n+2 Nie i < n+1 stop Tak e[ 1]...  e[i-1] , i Umieść e[i] wśród elementów e[1],e[2],...e[i-1], przesuwając elementy większe o jedno miejsce w prawo, tak by ciąg i-pierwszych elementów był uporządkowany e[ 1]...  e[i-1]  e[i] , i e[ 1]... e[i-2] e[i-1], i i := i+1 litopad 2002 G. Mirkowska, ASD 05 Sortowanie

9 Algorytm Insertion_sort{for i := 2 to n do j := i; pom := e[i]; while ( j>1 andif e[j-1]> pom ) do e[j] := e[j-1]; j := j-1 od; e[j] := pom od} e[ 1]...  e[i-1] e[ 1]...  e[j-1] pom=e[i], j=i pom< e[ j+1]...  e[i], pom Analiza pętli wewnętrznej Pom < e[ j]e[j+1]...  e[i] pom< e[ j+1]...  e[i] e[ 1]  ...  e[j-1]  pom< e[ j+1]...  e[i] e[ 1]  ...  e[j-1]  e[j] < e[ j+1]...  e[i] litopad 2002 G. Mirkowska, ASD 05 Sortowanie

10 Poprawność sortowania przez wstawianieAlgorytm sortowania przez wstawianie poprawnie rozwiązuje problem sortowania w każdej liniowo uporządkowanej strukturze danych. Twierdzenie Algorytm sortowania przez wstawianie jest, w każdej liniowo uporządkowanej strukturze danych, całkowicie poprawny ze względu na warunek początkowy n>0 i warunek końcowy (1 litopad 2002 G. Mirkowska, ASD 05 Sortowanie

11 Koszt sortowania przez wstawianieOperacja dominująca - porównywanie elementów. W(n) = i=2...n (koszt maksymalny pętli wewnętrznej) = i=2...n (i-1) = n(n-1)/2 = O(n2) Element pom z prawdopodobieństwem 1/i może zająć dowolną z pozycji od 1 do i. A(n) = i=2...n (koszt średni pętli wewnętrznej)= = i=2...n (j=1...i j*(1/i)) = i=2...n (1/i)(i (i+1))/2 = (n+1)(n+2)/ = (1/4)n2 +O(n) Algorytm sortuje w miejscu. litopad 2002 G. Mirkowska, ASD 05 Sortowanie

12 Sortowanie przez scalanieIdea : dziel i zwyciężaj ! (1) Dzielimy zadanie posortowania całego ciągu na dwa podzadania: posortowania jego lewej i prawej połowy. (2) Gdy obie części tworzą już ciągi uporządkowane, wtedy scalamy je otrzymując rozwiązanie. litopad 2002 G. Mirkowska, ASD 05 Sortowanie

13 G. Mirkowska, ASD 05 SortowaniePrzykład 16 5 12 4 10 6 1 13 5 16 4 12 6 10 1 13 i.t.d. litopad 2002 G. Mirkowska, ASD 05 Sortowanie

14 G. Mirkowska, ASD 05 SortowanieOperacja scalania Dane są dwa ciągi X i Y, uporządkowane niemalejąco, x1,...xn i y1,...ym. Utworzyć ciąg e=e1,...e n+m złożony z elementów obu ciągów uporządkowany niemalejąco. Wp = {n>0 m>0, x1... xn i y1... ym } Wk = { e1...  en+m , (in+m)( j)( ei= xj lub ei = yj)} X : Y : Przykład 1 2 3 4 5 6 7 8 9 litopad 2002 G. Mirkowska, ASD 05 Sortowanie

15 G. Mirkowska, ASD 05 SortowanieAlgorytm scalania {i:=1; j := 1; k :=1, while (i  n and j  m) do if x[i]< y[j] then e[k] := x[i]; i := i else e[k] := y[j]; j := j fi; k := k+1; od; Niezmiennik {k= i+j-1, e[1]...  e[k-1] i wszystkie elementy x[1],...,x[i-1] oraz y[1],...,y[j-1] zostały już umieszczone na pozycjach od 1 do k-1 w ciągu e .} if ( j > m) then for i := i to n do e[k] := x[i]; k := k od Else for j := j to m do e[k] := y[j]; k := k od} Koszt : O(n+m) litopad 2002 G. Mirkowska, ASD 05 Sortowanie

16 Specyfikacja procedury scal(k,x,l)Wersja procedury scal (k,x,l) użyta w algorytmie Sortowania przez scalanie ma następującą specyfikację Wp = {k  x  l  e[k]  e[k+1]  … e[x]  e[x+1]  e[x+2] … e[l]} Wk = {e[k] e[k+1]  …e[x] e[x+1] … e[l] } Twierdzenie (*) Procedura scal(k, x,l) zastosowana do dowolnego ciągu e[1],...,e[n] jest całkowicie poprawna ze względu na podaną wyżej specyfikację. litopad 2002 G. Mirkowska, ASD 05 Sortowanie

17 Sortowanie przez scalanieJeśli k=l, to jest tylko jeden element w naszym ciągu. procedure MS(k,l : integer); begin if l>k then x := (k+l) div 2; MS(k,x); MS(x+1,l); scal (k,x,l) fi end MS; W tym wywołaniu rozważamy lewą „połowę” danego ciągu Merge-sort Z założenia indukcyjnego : e[k] ...  e[x] Z założenia indukcyjnego :e[x+1] ...  e[l] Na mocy Tw (*) : e[k] ...  e[l] W tym wywołaniu rozważamy prawą „połowę” danego ciągu litopad 2002 G. Mirkowska, ASD 05 Sortowanie

18 Koszt algorytmu Merge_SortZałóżmy, że n = 2 p. wtedy T(n) = T(n/2) + T(n/2) + cn T(1) = 0 Po podstawieniu mamy T(2 0) = 0 T(2 p) = 2 T(2 p-1) +c n T(2 p ) = 2 T(2 p-1) + c2 p = 2(2T(2 p-2) +c 2 p-1) + c2 p = 2 2 T(2p-2 ) + c2 p + c2 p = ...= 2 p T(2 0 ) + cp 2 p = ( n lg n) T(n) = (n lg (n)) Ostatecznie : litopad 2002 G. Mirkowska, ASD 05 Sortowanie