Aplet
Kluczowym elementem algorytmu sortowania szybkiego jest funkcja podziału (podzielTablicę). Jej zadaniem jest rozłożenie wartości tak, aby po lewej stronie znajdowały się wartości mniejsze od zmiennej pivot, a po prawej – większe. Sposób wyboru elementu pivot może być deterministyczny (weź zawsze i‑ty element) lub losowy (weź losowy element) – zaprezentowany przykład jest niezależny od metody wyboru. Możemy nieformalnie opisać tę funkcję w następujący sposób:
Dla tak zapisanej funkcji podziału algorytm quick sort można określić następująco.
Zapoznaj się z apletem prezentującym szukanie piwotu.
Uruchom aplet prezentujący kroki wykonywane przez algorytm sortowania szybkiego w wyżej przedstawionym wariancie. Sprawdź działanie dla domyślnego przykładu. Wpisz własne wartości tablicy (maks. dł. 15) z przedziału [-99,99] i sprawdź działanie dla różnych zestawów danych. Znajdź pesymistyczny przykład, dla którego algorytm zostanie wykonany w czasie .
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DNd9FlVmO
Aplet prezentuje kroki wykonywane przez algorytm sortowania szybkiego w wyżej przedstawionym wariancie. Sprawdźmy działanie dla domyślnego przykładu. Wpiszemy własne wartości tablicy (maks. dł. 15) z przedziału [-99,99] i sprawdzimy działanie dla różnych zestawów danych. Znajdziemy pesymistyczny przykład, dla którego algorytm zostanie wykonany w czasie
Na samej górze apletu znajduje się pole: Wartości tablicy.
W polu tym wpisano ciąg liczb: -48, -43, -30, -15, 7, 7, -37.
Pod polem Wartości tablicy znajdują się przyciski Cofnij oraz Dalej.
Poniżej znajdują się kwadratowe bloki zawierające Wartości tablicy:
-48, -43, -30, -15, 7, 7, -37.
Blok zawierający wartość -37 podpisany jest jako pivot.
Po kliknięciu przycisku dalej odpowiednią liczbę razy, pojawiły się strzałki wychodzące od bloku z wartością -15, które wskazują na nowe bloki poniżej z wartościami:
-48, -43, -37, -30, -15, 7, 7.
Blok z wartością -37 zmienił kolor na szary, a bloki z liczbami -43 i 7 podpisane są jako pivot.
Następnie po lewej oraz prawej stronie od szarej wartości -37, wychodzą strzałki wskazujące na dwa oddzielne rzędy bloków wypełnione wartościami:
Rząd pierwszy: -48, -43.
Rząd drugi: -30, -15, 7, 7.
Blok z wartością -15 podpisany jest jako pivot.
Bloki z wartościami -43, 7, 7 zmieniły kolor na szary.
Następnie od bloków o wartościach: -30, -15 wychodzą dwie strzałki wskazujące na ostatni rząd zawierający dwa bloki z liczbami:
-30, -15.
Wartość -15 jest koloru szarego.