Aisd W9

Algorytmy i struktury danych Temat: Algorytmy sortowania wewnętrznego

Metody sortowania wewnętrznego Podstawowe algorytmy sortowania
Sortowanie przez wstawianie (ang. insertion sort)
Sortowanie przez wybieranie (selekcję) (ang. selection sort)
Sortowanie przez zamianę (bąbelkowe) (ang. exchange sort, bubble sort) Efektywne algorytmy sortowania
Sortowanie przez kopcowanie (ang. heap sort)
Sortowanie metodą malejących przyrostów (Shella)
Sortowanie szybkie (ang. quicksort)
Sortowanie przez scalanie (ang. merge sort)

Klucze początkowe

Algorytmy i struktury danych

44

55

12

42

94

18

06

67 2

Sortowanie przez wstawianie

K r o k i a l g o r y t m u

Klucze początkowe

44

55

12

42

94

18

06

67

i=2

44

55

12

42

94

18

06

67

i=3

12

44

55

42

94

18

06

67

i=4

12

42

44

55

94

18

06

67

i=5

12

42

44

55

94

18

06

67

i=6

12

18

42

44

55

94

06

67

i=7

06

12

18

42

44

55

94

67

i=8

06

12

18

42

44

55

67

94

Algorytmy i struktury danych

3

Idea algorytmu sortowania przez wstawianie void InsertionSort (int tab[ ], int n) { for ( i=1; i
Algorytmy i struktury danych

4

Przykładowy algorytm sortowania przez wstawianie void InsertionSort (int tab[ ], int n) { for ( int i=1, j; i0 && temp
Algorytmy i struktury danych

5

Sortowanie przez wybieranie

44

55

12

42

94

18

06

67

06

55

12

42

94

18

44

67

i=3

06

12

55

42

94

18

44

67

i=4

06

12

18

42

94

55

44

67

i=5

06

12

18

42

44

55

94

67

i=6

06

12

18

42

44

55

67

94

Klucze K r początkowe o i=2 k i

a l g o r y t m u

Algorytmy i struktury danych

6

Idea algorytmu sortowania przez wybieranie void SelectionSort (int tab[ ], int n) { for (i=0; i
Algorytmy i struktury danych

7

Przykładowy algorytm sortowania przez wybieranie void SelectionSort (int tab[ ], int n) { for (int i=0, least, j; i
8

Przykładowy algorytm sortowania przez wybieranie void SelectionSort (int tab[ ], int n) ??? { for (int i=0, least, j; i
9

Sortowanie przez zamianę (bąbelkowe) Kroki Klucze i=2 początkowe

algorytmu

i=3

i=4

i=5

i=6

i=7

i=8

44

06

06

06

06

06

06

06

55

44

12

12

12

12

12

12

12

55

44

18

18

18

18

18

42

12

55

44

42

42

42

42

94

42

18

55

44

44

44

44

18

94

42

42

55

55

55

55

06

18

94

67

67

67

67

67

67

67

67

94

94

94

94

94

Algorytmy i struktury danych

10

Idea algorytmu sortowania przez zamianę void BubbleSort (int tab[ ], int n) { for (i=0; ii; j−−) jeśli kolejność elementów j oraz j-1 jest niewłaściwa, zamień je miejscami; }

Algorytmy i struktury danych

11

Przykładowy algorytm sortowania przez zamianę void BubbleSort (int tab[ ], int n) { for (int i=0; ii; j−− −−) −− if (tab[j]
Algorytmy i struktury danych

12

Sortowanie mieszane Kroki

Klucze początkowe i=2

algorytmu

i=3

i=4

44

06

06

06

06

55

44

44

12

12

12

55

12

44

18

42

12

42

18

42

94

42

55

42

44

18

94

18

55

55

06

18

67

67

67

67

67

94

94

94

Algorytmy i struktury danych

13

Przykładowy algorytm sortowania mieszanego void ShakeSort (int tab[ ], int n) { int left=0, right=n-1, k=n-1; do { for (int j= right; j>left; j−− −−) −− if (tab[j-1]>tab[j ]) { zamiana (tab[j −1], tab[j ]); k=j; } left=k+1; for (j= left; jtab[j ]) { zamiana (tab[j −1], tab[j ]); k=j; } right=k-1; } while (left
14

ZłoŜoność obliczeniowa algorytmów sortowania



Sortowanie przez wstawianie przypadek optymistyczny: dane są właściwie posortowane

void InsertionSort (int tab[ ], int n) { n -1 for ( int i=1, j; i0 && temp
∑

∑

} n - liczba elementów w tablicy, TO - liczba porównań związanych z tab, TR - liczba przypisań związanych z tab Algorytmy i struktury danych

15

ZłoŜoność obliczeniowa algorytmów sortowania 

Sortowanie przez wstawianie Przypadek pesymistyczny: dane są posortowane w odwrotnej kolejności

n −1 i n −1 void InsertionSort (int tab[ ], int n) TOmax = 1 = i = 1 + 2 + ... + n − 1 = { i =1 j =1 i =1 for ( int i=1, j; i0 && temp
∑∑

∑

}

Algorytmy i struktury danych

∑

∑

∑

= 2(n − 1) + 1 + 2 + ... + n − 1 = n(n − 1) = 2(n − 1) + = 0,5 (n2 + 3 n - 4) = O(n 2 ) 2 16

ZłoŜoność obliczeniowa algorytmów sortowania



Sortowanie przez wstawianie Przypadek „średni”

TOśr = 0.25 (n2 + n - 2)






TRśr = 0.25 (n2 + 5n - 6)

n - ilość elementów w tablicy, TO - liczba porównań klucza, TR - liczba przesunięć elementów w tablicy

Algorytmy i struktury danych

17

ZłoŜoność obliczeniowa algorytmów sortowania, cd.



Sortowanie przez wybieranie Przypadek optymistyczny = przypadek pesymistyczny

void SelectionSort (int tab[ ], int n) n −2 n −1 n −2 TO min = TO max = 1 = ( n −1 − i ) = { i =0 j = i +1 i =0 for (int i=0, least, j; i
∑∑ ∑

Algorytmy i struktury danych

18

ZłoŜoność obliczeniowa algorytmów sortowania, cd.



Sortowanie przez zamianę (bąbelkowe) Przypadek optymistyczny

void BubbleSort (int tab[ ], int TOn) min = TO max = { n −2 n −1 n −2 n( n − 1 ) for (int i=0; i i; j--) if (tab[j]
∑∑

Algorytmy i struktury danych

∑

19

ZłoŜoność obliczeniowa algorytmów sortowania, cd.



Sortowanie przez zamianę (bąbelkowe) Przypadek pesymistyczny

void BubbleSort (int tab[ ], intTO n)min = TO max = { n −2 n −1 n −2 n( n − 1 ) for (int i=0; ii; j--) i =0 j =i if (tab[j]
∑∑

∑∑

i =0 j = i +1

Algorytmy i struktury danych

∑

2

20

ZłoŜoność obliczeniowa algorytmów sortowania, cd.



Sortowanie przez zamianę (bąbelkowe) Przypadek „średni”

TO = 0,5 (n2 - n)

TRśr = 0,75 (n2 - n)

n - ilość elementów w tablicy, TO - liczba porównań klucza, TRi - liczba przesunięć elementów w tablicy

Algorytmy i struktury danych

21

Metody sortowania wewnętrznego

Efektywne algorytmy sortowania  Sortowanie przez kopcowanie (ang. heap sort)  Sortowanie metodą malejących przyrostów (Shella)  Sortowanie szybkie (ang. quicksort)  Sortowanie przez scalanie (ang. merge sort)

Algorytmy i struktury danych

22

Sortowanie drzewiaste 94

94

55 55

44

42

55

Tablica wynikowa:

12

94

42

...

94

67

18

06

67

94

Wyznaczenie największego klucza poprzez wielokrotny wybór Algorytmy i struktury danych

23

Sortowanie drzewiaste

55 55

44

42

55

Tablica wynikowa:

12

67

42

...

18

06

67

94

Zdjęcie z kopca największego klucza Algorytmy i struktury danych

24

Sortowanie drzewiaste 67

67

55 55

44

42

55

Tablica wynikowa:

12

18

42

...

67

18

06

67

94

Utworzenie nowego kopca Algorytmy i struktury danych

25

Sortowanie drzewiaste

55 55

44

42

55

12

Tablica wynikowa:

18

42

...

67

18

06

94

Zdjęcie z kopca największego klucza Algorytmy i struktury danych

26

Sortowanie drzewiaste 55

18

55 55

44

42

55

Tablica wynikowa:

12

18

42

...

67

6

18

6

94

Utworzenie kolejnego kopca itd. Algorytmy i struktury danych

27

Sortowanie przez kopcowanie 





Metodę sortowania drzewiastego udoskonalił J.Williams (1964) Sortowanie przez kopcowanie (ang. heap sort) dowolnej tablicy A składa się z dwóch etapów: 1. Najpierw tablicę A przetwarzamy na tablicę reprezentującą kopiec 2. Następnie w pętli od 0 do n-1 wywołujemy funkcję usuwania z kopca (tablicy A) elementu największego; Po wykonaniu ostatniego punktu tablica A posortowana jest rosnąco

Algorytmy i struktury danych

28

Sortowanie przez kopcowanie Przekształcanie tablicy w kopiec (tzw. metodą wstępującą R.Floyda (1964)): for (i=indeks ostatniego węzła-nie liścia; i>=0; i--)


odtwórz warunki kopca dla drzewa, którego korzeniem jest data[ i ] wywołując funkcję MoveDown(data, i, n-1);

Algorytmy i struktury danych

29

Sortowanie przez kopcowanie Działanie algorytmu sortowania przez kopcowanie dla tablicy [15 12 6 11 10 2 3 1 8] Krok 1

15

Zamiana korzenia z ostatnim elementem

6

12 11

1

10

2

3

8 15

Algorytmy i struktury danych

12

6

11

10

2

3

1

8

30

Sortowanie przez kopcowanie Krok 2 Zdjęcie z kopca elementu największego

8

6

12 11

1

10

2

3

15 8

Algorytmy i struktury danych

12

6

11

10

2

3

1

15

31

Sortowanie przez kopcowanie Krok 3 Przywrócenie drzewu własności kopca

12

6

11 8

1

10

2

3

15 12

Algorytmy i struktury danych

11

6

8

10

2

3

1

15

32

Sortowanie przez kopcowanie Krok 4 Zamiana korzenia z ostatnim elementem

1

6

11 8

12

10

2

3

15 1

Algorytmy i struktury danych

11

6

8

10

2

3

12

15

33

Sortowanie przez kopcowanie Krok 5 Przywrócenie drzewu własności kopca

11

6

10 8

12

1

2

3

15 11

Algorytmy i struktury danych

10

6

8

1

2

3

12

15

34

Sortowanie przez kopcowanie Krok 6 Zamiana korzenia z ostatnim elementem

3

6

10 8

12

1

2

11

15 3

Algorytmy i struktury danych

10

6

8

1

2

11

12

15

35

Sortowanie przez kopcowanie Krok 7 Przywrócenie drzewu własności kopca

10

6

8 3

12

1

2

11

15 10

Algorytmy i struktury danych

8

6

3

1

2

11

12

15

36

Sortowanie przez kopcowanie Krok 8 Zamiana korzenia z ostatnim elementem

2

6

8 3

12

1

10

11

15 2

Algorytmy i struktury danych

8

6

3

1

10

11

12

15

37

Sortowanie przez kopcowanie Krok 9 Przywrócenie drzewu własności kopca

8

6

3 2

12

1

10

11

15 8

Algorytmy i struktury danych

3

6

2

1

10

11

12

15

38

Sortowanie przez kopcowanie Krok 10 Zamiana korzenia z ostatnim elementem

1

6

3 2

12

8

10

11

15 1

Algorytmy i struktury danych

3

6

2

8

10

11

12

15

39

Sortowanie przez kopcowanie Krok 11 Przywrócenie drzewu własności kopca

6

1

3 2

12

8

10

11

15 6

Algorytmy i struktury danych

3

1

2

8

10

11

12

15

40

Sortowanie przez kopcowanie Krok 12 Zamiana korzenia z ostatnim elementem

2

1

3 6

12

8

10

11

15 2

Algorytmy i struktury danych

3

1

6

8

10

11

12

15

41

Sortowanie przez kopcowanie Krok 13 Przywrócenie drzewu własności kopca

3

1

2 6

12

8

10

11

15 3

Algorytmy i struktury danych

2

1

6

8

10

11

12

15

42

Sortowanie przez kopcowanie Krok 14 Zamiana korzenia z ostatnim elementem

1

3

2 6

12

8

10

11

15 1

Algorytmy i struktury danych

2

3

6

8

10

11

12

15

43

Sortowanie przez kopcowanie Krok 15 Przywrócenie drzewu własności kopca

2

3

1 6

12

8

10

11

15 2

Algorytmy i struktury danych

1

3

6

8

10

11

12

15

44

Sortowanie przez kopcowanie Krok 16 Zamiana korzenia z ostatnim elementem – sortowanie zakończone

1

3

2 6

12

8

10

11

15 1

Algorytmy i struktury danych

2

3

6

8

10

11

12

15

45

Sortowanie przez kopcowanie Idea algorytmu sortowania przez kopcowanie (ang. heap sort): heapsort(data[ ] ,n ) 1) przekształć tablicę w kopiec; 2) for (i=n-1; i>1; i--) { zamień korzeń z elementem na pozycji i; odtwórz własność kopca dla drzewa data[0], data[1], ..., data[i-1];

}

Algorytmy i struktury danych

46

Sortowanie przez kopcowanie Algorytm sortowania przez kopcowanie void heapsort( T data[ ], int n) { int i for (i=n/2-1; i>=0; i--) // utworzenie kopca MoveDown(data, i, n-1); for (i=n-1; i>=1; i--) { Swap(data[ 0 ],data[ i ]); // zdjęcie korzenia z kopca MoveDown(data, 0, i -1); // przywrócenie własności kopca } } Algorytmy i struktury danych

47

Sortowanie przez kopcowanie Analiza metody sortowania przez kopcowanie  

dla duŜych n metoda jest bardzo efektywna złoŜoność czasowa algorytmu (nawet w najgorszym przypadku): T(n)= O(n log2 n)

Algorytmy i struktury danych

48

Sortowanie metodą malejących przyrostów (Shella)

 Podstawą działania algorytmu sortowania Shella jest dzielenie tablicy na podtablice, zawierające elementy oddalone od siebie o h pozycji;  Idea algorytmu: określ liczby ht, ht-1, ..., h1 określające sposób podziału tablicy Tab na podtablice; for (h= ht; t > 1; t--, h= ht) podziel Tab na h podtablic; for (i=1; i≤ ≤h; i++) posortuj i-tą podtablicę; // dowolną metodą posortuj tablicę Tab; // dowolną metodą

Algorytmy i struktury danych

49

Sortowanie metodą malejących przyrostów (Shella)  sortowanie podtablic moŜe być realizowane dowolną metodą sortowania (najczęściej wykorzystuje się sortowanie przez wstawianie);  tablica wyjściowa dzielona jest na ht podtablic, tworzonych co ht-ty element; powstaje zatem ht podtablic, przy czym dla kaŜdej wartości h=1, 2, ..., ht zachodzi:

Tab h h [i] = Tab[i ⋅ h t + h − 1] t

 np. dla ht=3 tablica Tab = [ Tab [0], Tab [1], Tab [2], Tab [3],... ] zostanie podzielona na 3 podtablice: Tab1, Tab2 oraz Tab3 w następujący sposób: Tab31[0]=Tab[0], Tab31[1]=Tab[3], ..., Tab31[i]=Tab[3*i], ... Tab32[0]=Tab[1], Tab32[1]=Tab[4], ..., Tab32[i]=Tab[3*i+1], ... Tab33[0]=Tab[2], Tab33[1]=Tab[5], ..., Tab33[i]=Tab[3*i+2], ...

 wszystkie podtablice sortowane są niezaleŜnie;  następnie tworzone są nowe podtablice, przy czym ht-1< ht Algorytmy i struktury danych

50

Sortowanie metodą malejących przyrostów (Shella) Przykład   

Tab=[ 5, 3, 6, 7, 2, 1, 9, 4, 8 ] ht=3 Wówczas: Tab1=[ 5, 7, 9 ] Tab2=[ 3, 2, 4 ] Tab3=[ 6, 1, 8 ]

Algorytmy i struktury danych

51

Sortowanie metodą malejących przyrostów (Shella) Przykład sortowania metodą malejących przyrostów (Shella) z przyrostami: 5, 3, 1 h=5

h=3

h=1

1 2 3 4 5 1 2 3 4 5 1 2 3 1 2 3 1

Algorytmy i struktury danych

10 10

8

6

20

4

3 3

8

22

1

0

1 20

0 4

3

15 10

8

16 22

1

6 0

8

1

0 0

8

20 4 4

10

0

10

4 3 4

20

16

15

6 6

22 8

10 10 8

16

20

6 1 1 3

6

15 15 15

6

3

4 1

22 22

4 1

0 0

16 16

22 6

3 3

15

15 10

8 15

16 20 20 16

22 20

16 22 52

Sortowanie metodą malejących przyrostów (Shella)  Algorytm Shella ma dwie cechy, które mogą ulegać zmianie w róŜnych implementacjach:  sekwencja wartości przyrostów,  algorytm sortowania wykorzystywany do sortowania podtablic;  dobrym rozwiązaniem (wynikającym z praktyki) jest wykorzystanie sekwencji przyrostów spełniających warunki: h1 = 1 hi+1 = 3 hi + 1

oraz zakończeniem dzielenia tablicy na podtablice dla takiego ht, dla którego zachodzi ht+2 ≥ n;  np. jeśli n=10000 sekwencja przyrostów ma postać: 1, 4, 13, 40, 121, 364, 1093, 3280 tzn. t=8; h9= 3 h8 + 1=9841; h10= 3 h9 + 1=29524 Algorytmy i struktury danych

53

Sortowanie metodą malejących przyrostów (Shella)  o złoŜoności algorytmu decyduje ht i sposób zmiany h


ht = 1 oznacza zwykłe sortowanie (np. przez wstawianie)




dla hi+1 = 3 hi + 1 (...., 40, 13, 4, 1 ) algorytm ma złoŜoność O(n1.25)




dla hi = 2i - 1 (..., 31, 15, 7, 3, 1 ) algorytm ma złoŜoność O(n1.2)

Algorytmy i struktury danych

54

Sortowanie metodą malejących przyrostów (Shella) Algorytm sortowania metodą malejących przyrostów (Shella) void ShellSort(T Tab[ ], int Size){ register int i, j hCnt, h; int increments[20], k; // stworzenie odpowiedniej liczby przyrostów h for (h=1, i=0; h<Size; i++){ increments[i]=h; h=3*h+1;} for (i--; i≥ ≥0; i--){ // pętla po wszystkich róŜnych przyrostach h h= increments[i]; for (hCnt=h; hCnt<2*h; hCnt++){ // pętla po liczbie podtablic „co h” w danym przebiegu for (j=hCnt; j<Size;){ // sortowanie przez wstawianie podtablicy T tmp=Tab[j]; k=j; while (k-h>=0 && tmp
Algorytmy i struktury danych

55

Sortowanie metodą malejących przyrostów (Shella)

 złoŜoność obliczeniowa algorytmu sortowania metodą malejących przyrostów (Shella) - O(n1,25)  zachodzi O(n2) ≥ O(n1,25) ≥ O(n log2 n)

Algorytmy i struktury danych

56

Sortowanie szybkie (quicksort)

Sortowanie szybkie (quicksort)  Metoda opracowana przez C.A.R. Hoarea  Podobnie jak metoda Shella zakłada dekompozycję tablicy na mniejsze podtablice (które jest łatwiej posortować)

Algorytmy i struktury danych

57

Sortowanie szybkie (quicksort)

Idea metody: Krok 1. Rozdzielić elementy danego ciągu e1, e2,... , en na dwie części względem pewnego ustalonego elementu, tzw. mediany (elementu osiowego), tak aby na lewo od niego znajdowały się elementy mniejsze, a na prawo elementy większe. Krok 2. Posortować elementy na lewo od mediany. Krok 3. Posortować elementy znajdujące się na prawo od mediany. Algorytmy i struktury danych

58

Sortowanie szybkie - przykład 10 5 7 8 14 12 3 4 1 Rozdzielanie ze względu na wybraną medianę Stosujemy rekurencyjnie tę samą zasadę do obu części

5 7 8 3 4 1 10 14 12 3 4 1 5 7 8

1 3 4

12 14

7 8

1 3 4 5 7 8 10 12 14 Algorytmy i struktury danych

59

Sortowanie szybkie (quicksort)

 Algorytm QuickSort jest typowym algorytmem rekurencyjnym;  W celu podzielenia tablicy konieczne jest wykonanie dwóch operacji:  znalezienie elementu osiowego (wyznaczającego podział tablicy na dwie podtablice),  przejrzeniu tablicy w celu umieszczenia jej elementów we właściwych podtablicach;  Wybór dobrego elementu osiowego nie jest zadaniem łatwym (obie podtablice powinny mieć zbliŜoną wielkość);  Najczęściej stosowane strategie wyboru elementu osiowego:  wybranie pierwszego elementu tablicy;  wybranie elementu znajdującego się pośrodku tablicy.

Algorytmy i struktury danych

60

Sortowanie szybkie (quicksort)

Algorytm QuickSort void QuickSort(int *Tab, int left, int right) { if (left < right) { int med=left; for ( int i=left+1; i < right; i++ ) if ( Tab[i] < Tab[left] ) Zamiana( Tab[++med], Tab[i] ); Zamiana( Tab[left], Tab[med] ); QuickSort(Tab, left, med-1); QuickSort(Tab, med+1, right); } } Algorytmy i struktury danych

61

Sortowanie szybkie (quicksort) Algorytm QuickSort - przykład 29

40

2

1

6

18

20

32

23

34

39

41

29 2

1

6

18

20

23

40

32

2 32 6

Algorytmy i struktury danych

2

39

41

40

1

1

34

6

18 18

20 20

34

39

41

23 23

29

32

34

39

40

41 62

Sortowanie szybkie – przypadek pesymistyczny  Przypadek pesymistyczny zachodzi wówczas, gdy wektor jest uporządkowany (np. rosnąco lub malejąco)  Pesymistyczna złoŜoność algorytmu QuickSort mierzona liczbą porównań wartości wynosi O(n 2)

Jeśli jako medianę wybiera się zawsze pierwszy element, to w wyniku rozdzielenia, jedna część „młodsza” będzie pusta , a druga „starsza” będzie zawierała o jeden element mniej niŜ w poprzednim kroku.

Koszt operacji rozdzielania dla n elementowego ciągu wynosi n-1 porównań.

n

T(n) = n − 1 + T(n − 1) = ∑ (i − 1) = O(n2 ) i=2

Algorytmy i struktury danych

63

Sortowanie szybkie – przypadek optymistyczny 

ZałoŜenie: n=2k, k=1,2,3,...



Przypadek optymistyczny ma miejsce wówczas, gdy tablice tablica jest dzielona na równe części



Średnia złoŜoność algorytmu QuickSort, wynosi wówczas T(n) = O(n lg n)



Liczba porównań w kolejnych iteracjach pętli wynosi:

T(n) = n + 2

n n n n + 2 ⋅ 2 + 2 ⋅ 2 ⋅ 2 + ... + n = 2 4 8 lg n n = n + ∑ n = n(1 + lg n) k =1

T(n) = O(n lg n) Algorytmy i struktury danych

64

Sortowanie szybkie – przypadek średni

Z badań wynika, Ŝe średnia złoŜoność algorytmu QuickSort jest bliŜsza przypadkowi optymistycznemu, tzn. wynosi T(n) = O(n lg n)

Algorytmy i struktury danych

65

Sortowanie przez scalanie (MergeSort)

Sortowanie przez scalanie (MergeSort)  Jeden z pierwszych algorytmów sortowania komputerowego;  Autor metody: John von Neumann  Podobnie jak metoda Shella zakłada dekompozycję tablicy na mniejsze podtablice (które jest łatwiej posortować)

Algorytmy i struktury danych

66

Sortowanie przez scalanie

Idea metody: (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.

Algorytmy i struktury danych

67

Sortowanie przez scalanie - przykład 16 5 12 4 10 6 1 13 15 7 1 14 9 3 8 11 16 5 12 4 10 6 1 13 16 5 12 4

10 6 1 13

16 5

12 4

10 6 1 13

5 16

4 12

6 10 1 13

4 5 12 16

15 7 1 14 9 3 8 11 15 7 1 14

9 3 8 11

1 6 10 13

1 4 5 6 10 12 13 16

1 3 7 8 9 11 14 15

1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Algorytmy i struktury danych

68

Sortowanie przez scalanie (MergeSort)

Idea scalania dwóch podtablic w jedną scal(Tab, pierwszy, ostatni) { srd=(pierwszy+ostatni)/2; i1=0; i2=pierwszy; i3=srd+1; while (zarówno prawa, jak i lewa podtablica zawierają elementy) if (Tab[i2]
69

Sortowanie przez scalanie (MergeSort)

Idea algorytmu MergeSort MergeSort(Tab, pierwszy, ostatni) { if (pierwszy , ostatni) } srd=(pierwszy+ostatni)/2; MergeSort(Tab, pierwszy, srd); MergeSort(Tab, srd+1, ostatni); scal(Tab, pierwszy, ostatni); } }

Algorytmy i struktury danych

70

Sortowanie przez scalanie (MergeSort)

ZłoŜoność obliczeniowa algorytmu MergeSort a a

T(1) = 0

n T(n) = 2T( ) + n 2

 MoŜna pokazać, Ŝe: T(n)=O(n log2n) (takŜe w przypadku pesymistycznym)

Algorytmy i struktury danych

71

Efektywne algorytmy sortowania ZłoŜoność sortowania

Algorytmy i struktury danych

72

Efektywne algorytmy sortowania ZłoŜoność sortowania

Algorytmy i struktury danych

73

Demonstracja algorytmów sortowania 

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

pokaz

Algorytmy i struktury danych

74

Algorytmy i struktury danych

75