Na ostatnich wykładach mówiliśmy o metodzie Shella. Dziś dokończymy to zagadnienie. Warto dodać jeszcze do tamtych informacji, że złożonośc obliczeniowa algorytmu sortowania metodą malejących przyrostów (Shella) równa jest
. Wówczas zachodzi tutaj:
. I teraz przejdźmy do omówienia sortowania szybkiego (quicksort). Metoda ta została opracowana przez C.A.R. Hoarea. Metoda ta podobnie, jak metoda Shella zakłada dekompozycje tablicy na mniejsze podtablice, które łatwiej jest posortować. Idea metody zawiera się w trzech krokach:

1. Należy rozdzielić elementy danego ciągu
   na dwie części względem pewnego ustalonego elementu - takzwanej mediany (elementu osiowego) tak, aby na lewo od niego znajdowały się elementy mniejsze, a na prawo elementy większe.

2. Należy posortować elementy na lewo od mediany.

3. Należy posortować elementy znajdujące się na prawo od mediany.

Oto jak wygląda przykład takiego sortowania:

Algorytm quicksort jest typowym algorytmem rekurencyjnym. W celu podzielenia tablicy konieczne jest tu wykonanie dwóch nastepujących operacji:

1. Znalezienie elementu osiowego (wyznaczającego podział tablicy na dwie podtablice).

2. Przejrzeniu tablicy w celu umieszczenia jej elementów we właściwych podtablicach.

Wybór dobrego elementu osiowego nie jest zadaniem łatwym, gdyz obie podtablice powinny mieć zblizoną wielkość. Najczęściej stosuje się dwie strategie wyboru elementu osiowego. Pierwsza to wybieranie pierwszego elementu tablicy, a druga - wybieranie elementu znajdującego się pośrodku tablicy. Oto algorytm sortowania szybkiego w postaci pseudokodu:

I jeszcze raz przykład:

Przypadek pesymistyczny dla sortowania szybkiego zachodzi wówczas, gdy wektor jest uporzadkowany (rosnąco lub malejąco). Pesymistyczna złożoność tego algorytmu mierzona liczbą porównań wartości wynosi
. Jeśli jako medianę wybiera się zawsze pierwszy element, to w wyniku rozdzielenia, jedna częśc młodsza będize pusta, a druga starsza będzie zawierała o jeden element mniej niż w poprzednim kroku. Spójrzmy na wzór dla ostatecznej wersji przypadku pesymistycznego (koszt operacji ropzdzielania dla n elementowego ciągu wynosi n - 1 porównań):

A teraz kolej na przypadek optymistyczny. Mamy następujące założenie:
. Przypadek optymistyczny ma miejsce wówczas, gdy tablica jest dzielona na równe części. Średnia złożonośc tego algorytmu wynosi wówczas
. Z kolei liczba porównań w kolejnych iteracjach pętli wynosi:

A zatem ostatecznie
. Kolej na przypadek średni. Z badań wynika, że srednia złożonośc algorytmu quicksort jest bliższa przypadkowi optymistycznemu, czyli wynosi
. Kolejną metodą jest sortowanie przez scalanie. Jest jednym z pierwszych algorytmów sortowania komputerowego. Autorem tej metody jest John von Neumann. Podobnie, jak metoda Shella algorytm ten zakłada podział tablicy na dwie mniejsze podtablice, które jest łatwiej posortować. Idea metody zawiera się w trzech punktach. Najpierw dzielimy sortowany ciąg na dwa podciągi. Potem sortujemy lewy i prawy podciąg stosując zasady rekurencji, a następnie scalamy dwa uporzadkowane podciągi otrzymując posortowany ciąg wyjściowy. Oto przykład:

Poniżej rysunek przedstawiający ideę scalania dwóch podtablic w jedną (obie podtablice są uporządkowane):

A oto kod to powyśzego rysunku o zlożoności T(n) = O(n):

A oto pseudokod dla całego algorytmu sortowania przez scalanie:

No i zlożonośc obliczeniowa tego algorytmu:
. Można by tu zatem pokazać, że
także w przypadku pesymistycznym.

A teraz przejdźmy do ostatniego już działu algorytmów sortowania, a mianowicie do sortowania zewnętrznego (cały czas mówiliśmy o wewnętrznym). I teraz nieco o sortowaniu danych w plikach zewnętrznych. Dane, które sa przechowywane w plikach zewnętrznych także mogą być sortowane. Wymaga to jednak strosowania nieco innych metod sortowania. Wynika to z innej organizacji dostepu do danych, które sa przechowywane w plikach zewnętrznych, gdzie ogranicza nas przede wszystkim sekwencyjność ich zapisu. Omówione na dzisiejszych wykładach zostana dwie takie metody sortowania danych w plikach zewnętrznych, a mianowicie metoda łączenia prostego i metoda łączenia naturalnego. Metoda łączenia prostego polega na sukcesywnym dzieleniu danych w pliku na podciągi (serie) o ustalonej długości maksymalnej i łączeniu tych podciągów wraz z równoczesnym porzadkowaniem zawartych w nich elementów w uporządkowane serie danych. Porządek ten może być dowolny (rosnący lub malejący). Zapis logiki algorytmu sortowania metodą łączenia prostego może być następujący:

Popatrzmy jak wygląda metoda łączenia prostego niemalejąco w poszczegolnych krokach:

I kolej na metodę łączenia naturalnego. Polega ona na sukcesywnym dzieleniu danych w pliku według uporzadkowanych podciągów i łączeniu tych podciągów wraz z równoczesnym porzadkowaniem zawartych w nich elementów. Nie ustala się tutaj długości podciągów - zależy to wyłącznie od ulożenia wartości sortowanych elementów. Oto zapis logiki algorytmu sortowania metodą łączenia naturalnego:

I przykład metody łączenia naturalnego niemalejąco:

---