• Wprowadzenie do algorytmów sortowania: sortowanie metodą bąbelkową, sortowanie przez proste wybieranie, sortowanie przez proste wstawianie.

• 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
zgodnie z relacją $\leq$ (rosnąco)
zgodnie z relacją $\geq$ (malejąco)

• 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

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
tablica posortowana algorytmem stabilnym (klucz: wiek)
tablica posortowana algorytmem niestabilnym (klucz: wiek)

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:

• Wizualizacja sortowania
• Wizualizacja efektywności

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.

• 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$.

Zalety:

• wydajny dla danych wstępne posortowanych
• wydajny dla zbiorów o niewielkiej liczebności
• małe zasoby zajmowane podczas pracy (sortowanie w miejscu¹⁾)
• stabilność
• prostota implementacji

Wady:

• mała efektywność dla normalnej i dużej ilości danych

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.

• 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.

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.

1. 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.
2. Powyższe operacje wykonujemy, aż dojdziemy do końca tabeli.
3. Następnie ponownie rozpoczynamy porównywanie elementów od początku tabeli.
4. Sortowanie kończymy, gdy podczas kolejnego przejścia przez całą tabelę nie wykonana zostanie żadna zamiana.

Zalety:

• prosta realizacja
• niskie zużycie pamięci (bo: sortowanie w miejscu)
• stabilność

Wady:

• mała efektywność obliczeń

Teoria i przykład

1. Który algorytm sortowania jest najefektywniejszy w sortowaniu danych uporządkowanych?
2. Który algorytm sortowania jest najefektywniejszy w sortowaniu danych odwrotnie posortowanych?
3. Który algorytm sortowania jest najefektywniejszy w sortowaniu danych przypadkowych?

(poziom trudności: )

Narysuj schemat blokowy sortujący tablicę metodą bąbelkową (bubble sort).

(poziom trudności: )

Narysuj schemat blokowy sortujący tablicę metodą przez proste wybieranie (selection sort).

(poziom trudności: )

Narysuj schemat blokowy sortujący tablicę metodą przez proste wstawianie (insertion sort).