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 (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 (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	2	3	4	5	5	2	3	1
	1	2	3	4	5
C	0	0	0	0	0

Stan po zliczeniu

	1	2	3	4	5	6	7	8
A	2	3	4	5	5	2	3	1
	1	2	3	4	5
C	1	2	2	1	2