Differences

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

--- dydaktyka:aisd:2016:sort [2016/05/25 15:37]
pkleczek
+++ — (current)
@@ Line 1: / Line 1: @@
-~~NOTRANS~~
-====== 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
-  * zakładamy, że chcemy otrzymać tablicę posortowaną rosnąco
-----
-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.sorting-algorithms.com/|Wizualizacja efektywności]]
-==== Sortowanie przez proste wybieranie ====
-Sortowanie przez proste wybieranie (ang. //selection 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 ===
-  * Przyjmujemy, że tablica złożona z elementów $a_1, a_2, \cdots, a_n$ jest umownie podzielona 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 szukamy w ciągu źródłowym najmniejszego elementu i zamieniamy go miejscem z elementem $a_i$.
-=== Przykład ===
-[{{:dydaktyka:aisd:2016:selection_sort_example.png?nolink|Schemat przebiegu sortowania tablicy sześciu liczb metodą przez proste wybieranie – 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 przez proste wstawianie ====
-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 ===
-  * Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
-  * Weź dowolny element ze zbioru nieposortowanego.
-  * Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
-  * Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
-  * Jeśli zbiór elementów nieuporządkowanych jest niepusty, wróć do punkt 2.
-=== Przykład ===
-[{{:dydaktyka:aisd:2016:insertion_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 zmianę miejsc elementów w danej rundzie.}}]
-==== 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 ====
-[[dydaktyka:aisd:2016:sort_quick-sort|Teoria i przykład]] (materiał dodatkowy)
-====== 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//).
-====== 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?

Joanna Jaworek-Korjakowska

User Tools

Site Tools

Differences

Page Tools