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

Ten algorytm mi się nie podoba…

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

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

Sortujemy 6-elementową tablicę tab:

Wywołanie funkcji QuickSort() ma postać QuickSort(tab, 0, 5)

Przykład - dla QuickSort(tab, 0, 5)

• wyznaczamy element środkowy: $\lfloor (0+5)/2 \rfloor = 2$, $x = tab[2] = 5$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• 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:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• 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]$: $\lfloor (2+3)/2 \rfloor = 2$, $x = tab[2] = 3$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• 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]$: $\lfloor (4+5)/2 \rfloor = 4$, $x = tab[4] = 6$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• rozmiar obu tablic do posortowania wynosi 1, więc nie ma nowych wywołań

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

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