SORTOWANIE PRZEZ SCALANIE(MERGE SORT)
1. Dziel: dzielimy ciąg o wielkości n elementów na dwa podciągu po n/2 elementów każdy
2. Zwyciężaj: sortujemy otrzymane podciągi, używając rekurencyjnie sortowania przez scalanie
3. Połącz: scalamy posortowane podciągi aż uzyskamy jeden posortowany ciąg.
DZIELENIE
SCALANIE
Przyjmijmy, że rozmiar pierwotnego problemu n jest potęgą dwójki. Wówczas w każdym kroku podziału dzielimy problem na podproblemy rozmiaru dokładnie n/2.
Sortowanie przez scalanie jednego elementu wykonuje się w czasie stały, natomiast jeśli mamy n>1 to musimy czas rozbić na trzy składniki:
1. Dziel – znajdujemy środek przedziału, co zajmuje czas stały czyli Q(1),
2. Zwyciężaj – wywołujemy rekurencyjnie sortowanie przez scalanie dla dwóch podtablic, każda rozmiaru n/1 daje to nam w sumie czas 2T(n/2).
3. Procedura merge sort działa w czasie Q(n) gdzie n=p-l+1 jest liczbą scalanych elementów.
Sortowanie szybkie – quicksort
1. Dziel: Tablica jest dzielona na dwie podtablice, w ten sposób że wybieramy element dzielący, zwany też pivotem i w jednej podtablicy umieszczamy elementy mniejsze bądź równe elementowi dzielącemu a w drugiej – elementy większe bądź równe elementowi dzielącemu.
2. Zwyciężaj: Dwie podtablice są sortowane za pomocą wywołań rekurencyjnych algorytmu quicksort.
3. Połącz: Ponieważ podtablice są już sortowane to nie trzeba już nic łączyć gdyż cała tablica jest posortowana
Pierwszy podział, element dzielący pierwszy wybrany z tablicy, wersja zgodna z kodem źródłowym.
Pierwszy podział, element dzielący pierwszy wybrany z tablicy. Wersja wykorzystująca dodatkową tablicę
Sortowanie przez zliczanie – Countingsort
Działanie algorytmu polega na zliczaniu wystąpień poszczególnych cyfr. Przeglądamy tablicę wyjściową A a ilość wystąpień zapisujemy w pomocniczej tablicy C, gdzie indeks tablicy będzie odpowiadał odpowiedniej cyfrze. Na początek tablicę pomocniczą zerujemy. Kiedy zostanie osiągnięty koniec tablicy wyjściowej to w tablicy pomocniczej znajduje się odpowiednia liczba wystąpień dla każdej cyfry. Wtedy wyliczamy pozycję poszczególnych cyfr i wpisujemy do tablicy wynikowej B. Zgodnie z danymi zawartymi w tablicy pomocniczej
Stan przed zliczaniem
1
2
3
4
5
6
7
8
A
C
0
Stan po zliczeniu
...
RezidentRnR