Differences

This shows you the differences between two versions of the page.

--- dydaktyka:aisd:2016:sort [2016/04/23 20:37]
pkleczek [Przykłady algorytmów sortowania]
+++ — (current)
@@ Line 1: / Line 1: @@
-====== Sortowanie ======
-===== Cel laboratorium =====
-  * Wprowadzenie do algorytmów sortowania: sortowanie metodą bąbelkową, sortowanie przez proste wybieranie, sortowanie przez proste wstawianie.
-===== Teoria =====
-==== Sortowanie - co to? ====
-  * **Sortowanie** polega na **uporządkowaniu** zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru.
-  * Najczęstszym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, sortowanie słów.
-  * W przypadku liczb, sortowanie polega na znalezieniu kolejności liczb zgodnej z relacją $\leq$ lub $\geq$
-  * W przypadku słów (nazw) sortowanie polega na ustawieniu ich w porządku //słownikowym// (lub //alfabetycznym//) zwanym także //leksykograficznym//.
-^ Rodzaj posortowania ^ Przykład (dla tablicy liczb) ^
-| brak | {{:dydaktyka:aisd:2016:numerical_array_sort_example_unsorted.png?direct|}} |
-| zgodnie z relacją $\leq$ (rosnąco) | {{:dydaktyka:aisd:2016:numerical_array_sort_example_leq.png?direct|}} |
-| zgodnie z relacją $\geq$ (malejąco) | {{:dydaktyka:aisd:2016:numerical_array_sort_example_geq.png?direct|}} |
-==== Po co stosować sortowanie? ====
-  * posortowane elementy można szybciej zlokalizować
-  * posortowane elementy można przedstawić w bardziej czytelny sposób (np. kolejność alfabetyczna nazwisk)
-  * posortowanie ułatwia wstawienie nowego elementu z zachowaniem porządku
-==== Stabilność algorytmu ====
-Algorytm nazywamy **stabilnym**, jeśli podczas sortowania zachowuje on kolejność występowania elementów o tym samym kluczu.
-**Przykład**
-^ Rodzaj posortowania ^ Tablica ^
-| tablica nieposortowana | {{:dydaktyka:aisd:2016:table_unsorted.png?nolink|}} |
-| tablica posortowana algorytmem stabilnym (klucz: wiek) | {{:dydaktyka:aisd:2016:table_stable-sort.png?nolink|}} |
-| tablica posortowana algorytmem niestabilnym (klucz: wiek) | {{:dydaktyka:aisd:2016:table_unstable-sort.png?nolink|}} |
-===== Przykłady algorytmów sortowania =====
-Uwagi do opisu algorytmów sortowania:
-  * w opisie algorytmów sortowania będą używane tablice liczb całkowitych
-  * wartość każdego sortowanego elementu jest jednocześnie kluczem sortowania
-  * analizując daną metodę będziemy brali pod uwagę liczbę porównań, w której uczestniczą elementy sortowanej tablicy
-----
-Jako uzupełnienie do zamieszczonych w kolejnych paragrafach opisów metod sortowania - proszę zapoznać się z animacjami:
-  * [[http://home.agh.edu.pl/~jaworek/Sortowania.htm|Wizualizacja sortowania]]
-  * [[http://www.home.umk.pl/~abak/wdimat/s/Compare.html|Wizualizacja efektywności]]
-==== Sortowanie przez proste wybieranie ====
-Sortowanie przez proste wstawianie (ang. //insertion sort//) to podstawowy algorytm sortowania, łatwy do zrozumienia i implementacji.
-Algorytm polega na pobraniu kolejnego elementu z danych wejściowych i wstawieniu go w odpowiednie miejsce w tabeli wynikowej.
-=== Algorytm metody ===
-  - Elementy są umownie podzielone na (posortowany) ciąg wynikowy: $(a_1, a_2, \cdots, a_{i-1})$ i (nieposortowany) ciąg źródłowy $(a_i, a_{i+1}, \cdots, a_{n})$
-  - W $i$-tym kroku pobieramy element z ciągu źródłowego: $a_i$
-  - Porównujemy ten element z kolejnymi elementami z ciągu wynikowego: $a_{i-1}$, $a_{i-2}$, $\cdots$
-  - Porównanie kończymy, gdy porównywany element jest mniejszy lub równy elementowi $a_i$ lub gdy dojdziemy do początku ciągu wynikowego.
-  - Wstawiamy element $a_i$ w odpowiednim miejscu ciągu wynikowego.
-=== Przykład ===
-[{{:dydaktyka:aisd:2016:selection_sort_example.png?nolink|Schemat przebiegu sortowania tablicy sześciu liczb metodą przez proste wstawianie – składa się z pięciu rund. Na pomarańczowo zaznaczono ciąg źródłowy, a na zielono - ciąg wynikowy. Strzałkami zaznaczono pary elementów, które podlegają zamianie.}}]
-=== Uwagi ===
-Zalety:
-  * wydajny dla danych wstępne posortowanych
-  * wydajny dla zbiorów o niewielkiej liczebności
-  * małe zasoby zajmowane podczas pracy (sortowanie w miejscu((Termin //sortowanie w miejscu// oznacza, że nie potrzeba osobnej tablicy do przechowywania posortowanych wartości - zamiana odbywa się w ramach początkowej tablicy.)))
-  * stabilność
-  * prostota implementacji
-Wady:
-  * mała efektywność dla normalnej i dużej ilości danych
-==== Sortowanie bąbelkowe ====
-Sortowanie bąbelkowe (ang. //bubble sort//) polega na porównywaniu ze sobą dwóch kolejnych elementów i - jeśli to konieczne - zamianie ich kolejności.
-Nazwa metody wzięła się stąd, że kolejne porównania powodują "wypychanie" kolejnego największego elementu na koniec.
-=== Algorytm metody (wersja podstawowa) ===
-  - Porównujemy pierwszy i drugi element tabeli i - jeśli trzeba - to zamieniamy je miejscami. Następnie podobnie porównujemy drugi i trzeci element i - jeśli to konieczne - zamieniamy je miejscami, itd.
-  - Powyższe operacje wykonujemy, aż dojdziemy do końca tabeli.
-  - Następnie ponownie rozpoczynamy porównywanie elementów od początku tabeli.
-  - Sortowanie kończymy, gdy podczas kolejnego przejścia przez całą tabelę nie wykonana zostanie żadna zamiana.
-=== Przykład ===
-[{{:dydaktyka:aisd:2016:bubble_sort_example.png?nolink|Schemat przebiegu sortowania tablicy sześciu liczb metodą bąbelkową – składa się z sześciu rund. Na czerwono zaznaczono pary elementów, które podlegają zamianie.}}]
-=== Uwagi ===
-Zalety:
-  * prosta realizacja
-  * niskie zużycie pamięci (bo: sortowanie w miejscu)
-  * stabilność
-Wady:
-  * mała efektywność obliczeń
-==== Sortowanie metodą quick-sort ====
-=== Algorytm metody ===
-  * Sortowanie odbywa się w dwóch fazach: **dzielenia** i **sortowania**
-  * W fazie dzielenia tablica jest dzielona na dwie części wokół pewnego elementu (nazywanego elementem centralnym).
-  * Wybieramy jeden element (losowo, choć może to być element środkowy), który nazwiemy $x$.
-  * Przeglądamy tablicę od lewej strony, aż znajdziemy element $a_i \geq x$, a następnie przeglądamy tablicę od prawej strony, aż znajdziemy element $a_j \leq x$.
-  * Zamieniamy miejscami elementy $a_i$ i $a_j$ i kontynuujemy proces przeglądania i zamiany, aż gdzieś w środku tablicy nastąpi spotkanie.
-  * W rezultacie otrzymujemy tablicę podzieloną na lewą część z wartościami mniejszymi od $x$ i na prawą część z wartościami większymi od $x$.
-  * Na tym kończy się faza podziały i rozpoczyna faza sortowania
-  * Faza sortowania zawiera dwa rekurencyjne wywołania tej samej funkcji sortowania: dla lewej i dla prawej części posortowanej tablicy.
-  * Rekurencja zatrzymuje się, gdy rozmiar tablicy do posortowania wynosi 1 (pojedynczy element na pewno jest posortowany).
-=== Przykład ===
-Sortujemy 6-elementową tablicę ''tab'':\\ {{:dydaktyka:aisd:2016:quick-sort_example_01.png?nolink|}}
-Wywołanie funkcji ''QuickSort()'' ma postać ''QuickSort(tab, 0, 5)''
-**Przykład - dla QuickSort(tab, 0, 5)**
-  * wyznaczamy element środkowy: $(0+5)/2 = 2$, $x = tab[2] = 5$
-  * od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:\\ {{:dydaktyka:aisd:2016:quick-sort_example_02.png?nolink|}}
-  * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_03.png?nolink|}}
-  * wywołujemy rekurencyjnie funkcję ''QuickSort()'' dla elementów z zakresów $[l,j]$ oraz $[i,r]$: ''QuickSort(tab, 0, 3)'', ''QuickSort(tab, 4, 5)''
-**Przykład - dla QuickSort(tab, 0, 3)**
-  * wyznaczamy element środkowy dla zakresu $[0,3]$: $(0+3)/2 = 1$, $x = tab[1] = 2$
-  * od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:\\ {{:dydaktyka:aisd:2016:quick-sort_example_04.png?nolink|}}
-  * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_05.png?nolink|}}
-  * wywołujemy rekurencyjnie funkcję ''QuickSort()'' tylko dla elementów z zakresu $[2,3]$ (gdyż po lewej stronie rozmiar tablicy do posortowania wynosi 1 oraz $[i,r]$): ''QuickSort(tab, 2, 3)''
-**Przykład - dla QuickSort(tab, 2, 3)**
-  * wyznaczamy element środkowy dla zakresu $[2,3]$: $(2+3)/2 = 2$, $x = tab[2] = 3$
-  * od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:\\ {{:dydaktyka:aisd:2016:quick-sort_example_06.png?nolink|}}
-  * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_07.png?nolink|}}
-  * rozmiar obu tablic do posortowania wynosi 1, więc nie ma nowych wywołań
-**Przykład - dla QuickSort(tab, 4, 5)**
-  * wyznaczamy element środkowy dla zakresu $[4,5]$: $(4+5)/2 = 4$, $x = tab[4] = 6$
-  * od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:\\ {{:dydaktyka:aisd:2016:quick-sort_example_08.png?nolink|}}
-  * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_09.png?nolink|}}
-  * rozmiar obu tablic do posortowania wynosi 1, więc nie ma nowych wywołań
-=== Uwagi ===
-Zalety:
-  * wysoka efektywność dla średniego przypadku
-Wady:
-  * bardzo mała efektywność dla najgorszego przypadku
-  * duże zasoby zajmowane w trakcie pracy (bo: wywołania rekurencyjne zajmują pamięć komputera)
-  * brak stabilności
-====== Pytania ======
-  - Który algorytm sortowania jest najefektywniejszy w sortowaniu danych uporządkowanych?
-  - Który algorytm sortowania jest najefektywniejszy w sortowaniu danych odwrotnie posortowanych?
-  - Który algorytm sortowania jest najefektywniejszy w sortowaniu danych przypadkowych?
-====== Zadania ======
-===== Zadanie BUBBLE =====
-([size=10]poziom trudności:[/size] {{stars>2/4}})
-Narysuj schemat blokowy sortujący tablicę metodą bąbelkową (//bubble sort//).
-===== Zadanie SELECT =====
-([size=10]poziom trudności:[/size] {{stars>2/4}})
-Narysuj schemat blokowy sortujący tablicę metodą przez proste wybieranie (//selection sort//).
-===== Zadanie INSERT =====
-([size=10]poziom trudności:[/size] {{stars>2/4}})
-Narysuj schemat blokowy sortujący tablicę metodą przez proste wstawianie (//insertion sort//).

Joanna Jaworek-Korjakowska

User Tools

Site Tools

Differences

Page Tools