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