Sortowanie szybkie (Quicksort)

Zadanie AL3.1 Tablicę A = [23, 6, 11, 12, 17, 19, 7, 18, 12, 14, 15] sortujemy sortowaniem szybkim (Quicksort). W jaki sposób będzie zmieniała się ta tablica w czasie pierwszego przebiegu funkcji Partition dokonującej podziału? Wskaż kolejne elementy, które są ze sobą zamieniane, oraz zaznacz, jak ostatecznie zostanie podzielona tablica.

Zadanie AL3.2 (4 pkt.)

1. Zaimplementuj algorytm sortowania szybkiego omówiony na wykładzie. (3 pkt.)

2. Zmierz i porównaj czasy działania sortowania dla dwóch rodzajów danych: dane losowe oraz dane skrajnie niekorzystne (np. liczby uprządkowane rosnąco lub malejąco). (1 pkt)

   Testy (pomiary czasu) powinny być wykonane dla różnych wielkości tablicy, np. 10000 elementów, 50000 elementów, 100000 elementów i 150000 elementów. Sugerowany sposób prezentacji wyników testów:

   rozmiar tablicy	czas - dane losowe	czas - dane niekorzystne
   10000
   50000
   itd.

Zadanie AL3.3 (4.5 pkt.) Zaimplementuj i przetestuj (3.5 pkt.) oraz porównaj czasy działania (1 pkt.) podstawowej wersji sortowania szybkiego i jednej ze zmodyfikowanych wersji, gdzie element wyznaczający podział jest:

1. skrajnie prawym elementem A[r] (pod)tablicy (wersja podstawowa);

2. wybranym pseudolosowo (RandomizedQuicksort);

3. medianą (czyli elementem środkowym co do wartości) z trzech następujących elementów tablicy: skrajnie lewego (A[p]), środkowego (A[p + (r−p)/2]), skrajnie prawego (A[r]).

Podobnie jak w zadaniu AL3.2, testy powinny być wykonane dla danych losowych i niekorzystnych, dla różnych wielkości tablicy (np. 10000,50000,100000 i 150000). Dla tego samego rodzaju danych należy zestawić czasy działania trzech wersji algorytmów. Sugerowany sposób prezentacji wyników testów:

DANE LOSOWE

rozmiar tablicy	czas - algorytm 1	czas - algorytm 2	czas - algorytm 3
10000
50000
itd.

DANE NIEKORZYSTNE

rozmiar tablicy	czas - algorytm 1	czas - algorytm 2	czas - algorytm 3
10000
50000
itd.

Zadanie AL3.4 (5 pkt.)

1. Zaimplementuj algorytm sortowania szybkiego omówiony na wykładzie. (3 pkt.)

2. Następnie zmodyfikuj ten algorytm zastępujac warunek p< r warunkiem p+c< r, gdzie c to pewna stała większa lub równa 0. Czyli dla tablic o rozmiarze takim, że p+c< r (czyli o rozmiarze większym od c+1) będą normalnie robione wywołania rekurencyjne, a w przy rozmiarze takim, że p+c >= r nie będzie wykonywana procedura Partition i rekursywne wywołania, a podtablice tego rozmiaru pozostaną nieposortowane. Dopiero po zakończeniu tak „zepsutego” sortowania szybkiego, cała tablica ma być dodatkowo sortowana algorytmem sortowania przez wstawianie (Insertion-sort). Przetestuj czy zmodyfikowany algorytm poprawnie sortuje.(1 pkt.)

3. Porównaj czasy działania algorytmu podstawowego oraz jego modyfikacji dla dwóch rodzajów danych: dane losowe oraz dane skrajnie niekorzystne (ciąg malejący). Podobnie jak w zadaniu AL3.3, dla tego samego rodzaju danych należy zestawić czasy działania dwóch wersji algorytmów. (1 pkt)

Zadanie AL3.5 (5 pkt.)

1. Zaimplementuj algorytm sortowania szybkiego omówiony na wykładzie. (3 pkt.)

2. Następnie zmodyfikuj ten algorytm zastępujac warunek p< r warunkiem p+c< r, gdzie c to pewna stała większa lub równa 0. Czyli dla tablic o rozmiarze takim, że p+c< r (czyli o rozmiarze większym od c+1) będzie normalnie wykonywana procedura Partition i wywołania rekurencyjne, a w przy rozmiarze takim, że p+c >= r niech będzie stosowane jakieś proste sortowanie, np. bąbelkowe czy przez wstawianie ale tylko na podtablicy od p do r. Przetestuj czy zmodyfikowany algorytm poprawnie sortuje.(1 pkt.)

3. Porównaj czasy działania algorytmu podstawowego oraz jego modyfikacji dla dwóch rodzajów danych: dane losowe oraz dane skrajnie niekorzystne (ciąg malejący). Podobnie jak w zadaniu AL3.3, dla tego samego rodzaju danych należy zestawić czasy działania dwóch wersji algorytmów. (1 pkt)