Algorytmy sortujące презентация

publikowane na łamach Portalu www.szkolnictwo.pl mogą być wykorzystywane przez jego Użytkowników wyłącznie w zakresie własnego użytku osobistego oraz do użytku w szkołach podczas zajęć dydaktycznych. Kopiowanie, wprowadzanie zmian, przesyłanie, publiczne odtwarzanie i wszelkie wykorzystywanie tych treści do celów komercyjnych jest niedozwolone. Plik można dowolnie modernizować na potrzeby własne oraz do wykorzystania w szkołach podczas zajęć dydaktycznych.

danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.
Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwieniu stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.
Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego.

w pewnym porządku (kolejności). Porządek ten możemy określić za pomocą relacji ≥ lub ≤ (albo dowolnej innej relacji porządkowej, która jednoznacznie wyznacza kolejność elementów w zbiorze). Równość jest konieczna w przypadku, gdy elementy zbioru mogą przyjmować takie same wartości. Na przykład zbiór liczb:
Z = { 1, 4, 4, 5, 6, 8, 8, 9 }
jest posortowany rosnąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja, w której element poprzedni jest mniejszy lub równy od elementu następnego
Odwrotnie, zbiór:
Z = { 9, 8, 7, 6, 4, 4, 2, 1, 0 }
jest posortowany malejąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja, w której element poprzedni jest większy lub równy od elementu następnego.
W przypadku, kiedy zbiór nie składa się z liczb, należy określić dla każdego elementu tzw. klucz (ang. key), wedłóg którego dokonywane jest sortowanie.
Klucz jest liczbą, dlatego obowiązują dla niego podane wcześniej zasady kolejności elementów.

pamięciowa) – określa statystycznie czas wykonywania algorytmu w zależności od liczby danych wejściowych.
Czasowa złożoność obliczeniowa wyrażana jest liczbą tzw. operacji dominujących, czyli takich, które mają bezpośredni wpływ na czas wykonywania algorytmu. Dzięki takiemu podejściu uniezależnia się czasową złożoność obliczeniową od szybkości komputera, na którym dany algorytm jest realizowany.
Złożoność obliczeniowa charakteryzowana jest przy pomocy tzw. notacji O (omikron). Zapis O( ) określamy mianem klasy złożoności obliczeniowej algorytmu.
Klasa czasowej złożoności obliczeniowej umożliwia porównywanie wydajności różnych algorytmów sortujących. Z reguły proste algorytmy posiadają wysoką złożoność obliczeniową - długo dochodzą do wyniku końcowego.
Algorytmy bardziej skomplikowane posiadają mniejszą złożoność obliczeniową - szybko dochodzą do rozwiązania.

Czasowa złożoność obliczeniowa

grupy:
Algorytmy sortujące w miejscu (ang. in place) - wymagają stałej liczby dodatkowych struktur danych, która nie zależy od liczby elementów sortowanego zbioru danych (ani od ich wartości). Dodatkowa złożoność pamięciowa jest klasy O(1). Sortowanie odbywa się wewnątrz zbioru. Ma to bardzo istotne znaczenie w przypadku dużych zbiorów danych, ponieważ mogłoby się okazać, iż posortowanie ich nie jest możliwe z uwagi na brak pamięci w systemie. Sortowanie w miejscu, jest bardzo dużą zaletą.
Algorytmy nie sortujące w miejscu - wymagają zarezerwowania w pamięci dodatkowych obszarów, których wielkość jest uzależniona od liczby sortowanych elementów lub od ich wartości. Tego typu algorytmy są zwykle bardzo szybkie w działaniu, jednakże wymagają dodatkowej pamięci. Dlatego może się okazać, iż taki algorytm nie będzie w stanie posortować dużego zbioru danych, ponieważ system komputerowy nie posiada wystarczającej ilości pamięci RAM.

Oprócz złożoności czasowej definiuje się również złożoność pamięciową. Określa ona ilość zasobów komputera, których wymaga dany algorytm w zależności od liczby danych wejściowych. Tutaj także ma zastosowanie notacja omikron. Podczas określania złożoności algorytmu należy wziąć pod uwagę oba typy złożoności obliczeniowej.

Pamięciowa złożoność obliczeniowa

kolejność elementów równych. Oznacza to, iż elementy o tych samych wartościach będą występowały w tej samej kolejności w zbiorze posortowanym, co w zbiorze nieposortowanym. Czasami ma to znaczenie, gdy sortujemy rekordy bazy danych i nie chcemy, aby rekordy o tym samym kluczu zmieniały względem siebie położenie.
sortowanie bąbelkowe (ang. bubblesort) – O(n2)
sortowanie przez wstawianie (ang. insertion sort) – O(n2)
sortowanie przez scalanie (ang. merge sort) – O(nlogn), wymaga O(n) dodatkowej pamięci
sortowanie przez zliczanie (ang. counting sort lub count sort) – O(n + k), wymaga O(n + k) dodatkowej pamięci
sortowanie kubełkowe (ang. bucket sort) – O(n), wymaga O(k) dodatkowej pamięci
sortowanie pozycyjne (ang. radix sort) – O(d(n + k)), gdzie k to wielkość domeny cyfr, a d szerokość kluczy w cyfrach. Wymaga O(n + k) dodatkowej pamięci
sortowanie biblioteczne (ang. library sort) – O(nlogn), pesymistyczny O(n2)

?

zostaje zachowana).
sortowanie przez wybór (ang. selection sort) O(n2) – może być stabilne po odpowiednich zmianach
sortowanie Shella – (ang. shellsort) złożoność nieznana
sortowanie grzebieniowe – (ang. combsort) złożoność nieznana
sortowanie szybkie – (ang. quicksort) Θ(nlogn), pesymistyczny O(n2); z wykorzystaniem algorytmu selekcji "mediana median" ("magicznych piątek") do wyszukiwania mediany, pesymistyczna złożoność to O(nlogn)
sortowanie introspektywne – (ang. introspective sort lub introsort) O(nlogn)
sortowanie przez kopcowanie – (ang. heapsort) O(nlogn)

obliczeniowej równą O(n2).
Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
Algorytm przedstawia się następująco:
wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
zamień wartość minimalną, z elementem na pierwszej pozycji (i)
Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.
Algorytm jest niestabilny. Sortowanie odbywa się w miejscu.

Sortowanie przez wybór - Selection Sort

?

zostały elementy zbioru, które zostały już posortowane.

Przykład

d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.
Dane wyjściowe
d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.
Zmienne pomocnicze
i, j - zmienne sterujące pętli, i, j ∈ N pmin - pozycja elementu minimalnego w zbiorze d[ ],  pmin ∈ N
Lista kroków
K01: Dla j = 1, 2, ..., n - 1: wykonuj K02...K04
K02:     pmin ← j
K03:     Dla i = j + 1,  j + 2, ..., n: jeśli d[i] < d[pmin], to pmin ← i
K04:     d[j] ↔ d[pmin]
K05: Zakończ

Specyfikacja problemu

indeksach od 1 do n - 1, w których zostaną umieszczone elementy minimalne. Na początku tej pętli zakładamy, iż elementem minimalnym jest element d[j] i zapamiętujemy jego indeks w zmiennej pmin.
W pętli numer 2 sterowanej zmienną i porównujemy pozostałe elementy zbioru z elementem d[pmin]. Jeśli element zbioru d[i] jest mniejszy od elementu d[pmin], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycję w pmin i kontynuujemy pętlę wewnętrzną.
Po zakończeniu pętli wewnętrznej pmin zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[pmin]. Dzięki tej operacji element minimalny znajduje się na swojej docelowej pozycji. Zwiększamy j przechodząc do kolejnego elementu zbioru i kontynuujemy pętlę zewnętrzną.

złożoności O(n2), sortowanie odbywa się w miejscu . Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:
wydajny dla danych wstępnie posortowanych
wydajny dla zbiorów o niewielkiej liczebności
stabilny
Algorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny.

element zbioru. Jednoelementowa lista jest zawsze uporządkowana.
Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.
Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.
Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.

Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:

utworzoną z pozostałych elementów [7 3 4 5 8]. Elementy listy uporządkowanej zaznaczyliśmy kolorem niebieskim. Puste miejsce zaznaczyliśmy kolorem żółtym:

d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.
Dane wyjściowe
d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.
Zmienne pomocnicze
i, j - zmienne sterujące pętli, i, j Î N x - zawiera wybrany ze zbioru element.
Lista kroków
K01: Dla j = n - 1, n - 2, ..., 1: wykonuj K02...K04
K02: x ← d[j];  i ← j + 1
K03: Dopóki ( i ≤ n )  ∧  ( x > d[i] ): wykonuj d[i - 1] ← d[i];  i ← i + 1
K04:     d[i - 1] ← x
K05: Zakończ

Specyfikacja problemu

ostatniej pozycji jest zalążkiem listy uporządkowanej. Dlatego licznik pętli nr 1 przyjmuje wartość początkową j = n - 1.
Ze zbioru wybieramy element d[j] i umieszczamy go w zmiennej pomocniczej x. Miejsce zajmowane przez ten element staje się puste.
Pętlę wewnętrzną rozpoczynamy od pozycji następnej w stosunku do j. Pozycja ta zawiera pierwszy element listy uporządkowanej, która tworzona jest na końcu sortowanego zbioru. Pętlę wewnętrzną przerywamy w dwóch przypadkach - gdy licznik pętli wyjdzie poza indeks ostatniego elementu w zbiorze lub gdy element wybrany, przechowywany w zmiennej pomocniczej x, jest mniejszy lub równy bieżąco testowanemu elementowi listy uporządkowanej (dla sortowania malejącego należy zastosować w tym miejscu relację większy lub równy).

i pętla zewnętrzna jest kontynuowana. Zauważ, iż pozycja tego miejsca w zbiorze jest równa i - 1.
Jeśli żaden z warunków przerwania pętli wewnętrznej nr 2 nie wystąpi, to przesuwamy bieżący element listy na puste miejsce i kontynuujemy pętlę wewnętrzną.
Podsumowując: pętla zewnętrzna wybiera ze zbioru kolejne elementy o indeksach od n - 1 do 1, pętla wewnętrzna szuka dla wybranych elementów miejsca wstawienia na liście uporządkowanej, po znalezieniu którego pętla zewnętrzna wstawia wybrany element na listę. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od n - 1 do 1, zbiór będzie posortowany.

Schemat blokowy c.d.

nie wyróżnia on przypadku posortowania zbioru w kierunku odwrotnym. Dla tego algorytmu złożoność czasowa nie zależy od rozkładu elementów w sortowanym zbiorze.
Przy sortowaniu przez wybór algorytm wykorzystuje fakt posortowania zbioru. Dla zbiorów w znacznym stopniu uporządkowanych klasa czasowej złożoności obliczeniowej algorytmu jest prawie liniowa. Czas sortowania takich zbiorów jest bardzo krótki.
Najbardziej niekorzystnym przypadkiem jest sortowanie zbioru posortowanego odwrotnie - czas sortowania jest najdłuższy. Czas sortowania zbioru o losowym rozkładzie elementów jest o połowę krótszy.
Algorytm sortowania przez wybór jest dużo lepszy od sortowania przez wstawianie w przypadku zbiorów w znacznym stopniu uporządkowanych. Również zbiory o losowym rozkładzie elementów będą posortowane szybciej. Jedynie w przypadku pesymistycznym, gdy zbiór jest posortowany odwrotnie, algorytm jest wolniejszy od algorytmu sortowania przez wybór. Te cechy czynią algorytm sortowania przez wstawianie zalecanym, prostym algorytmem sortującym klasy O(n2).

Podsumowanie

W prezentacji przedstawiono dwa rodzaje algorytmów: algorytm stabilny – na przykładzie sortowania przez wstawianie i algorytm niestabilny - na przykładzie sortowania przez wybór.

Approach. Second Edition, Prentice Hall.
Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928)
John L Casti: Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience, 1996
Donald E. Knuth: Sztuka programowania. T. 1. Warszawa: Wydawnictwo Naukowo-Techniczne, 2002
Neil Gershenfeld i Isaac L. Chuang, Molekularne komputery kwantowe; Świat Nauki, sierpień 1998
Nadrian C. Seeman, Na granicy życia i nanotechnologii; Świat Nauki, lipiec 2004
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów;WNT, wyd. VI 2004
pl.wikipedia.org/
algorytm.org/
neuralnets.eu/
wazniak.mimuw.edu.pl/index.php?title=Sztuczna_inteligencja
computerchess.us/gtchess
encyklopedia.pwn.pl/lista.php?co=rekurencja