I_R_W14_M27_C++ Metoda Quicksort
Działanie algorytmu quick sort
Szybkie sortowanie, znane jako Quicksort, to jeden z najszybszych i najczęściej stosowanych algorytmów sortowania danych. Jego skuteczność opiera się na zasadzie „dziel i zwyciężaj”.
W animacji zobaczysz, jak algorytm wybiera element pivot, a następnie dzieli tablicę na dwie części:
elementy mniejsze lub równe pivotowi,
oraz elementy większe od pivota.
Każda z tych części jest następnie sortowana rekurencyjnie w ten sam sposób, aż do uzyskania w pełni uporządkowanej tablicy.
Dzięki temu podejściu Quicksort osiąga bardzo dobrą wydajność w praktyce i jest powszechnie wykorzystywany w systemach operacyjnych, bibliotekach standardowych oraz aplikacjach przetwarzających duże zbiory danych.
Animacja krok po kroku pokazuje cały proces – od pierwszego podziału, przez kolejne wywołania rekurencyjne, aż do uzyskania posortowanego wyniku.
Film dostępny pod adresem /preview/resource/R6T71PH1Q9RPU
Animacja przedstawia sortowanie wąskich kolumn od najniższej do najwyższej. Sortowanie przebiega bardzo szybko. Początkowo kolumny podlegające sortowaniu są różnej wielkości, są wymieszane. Następnie za pomocą przemieszczającej się strzałki w postaci łuku kolumny są porównywane i przestawiane od najniższej do najwyższej.
Dziel: tablicę wejściową podziel na dwie podtablice, od indeksu
pdo indeksuq, tak aby przed elementem o indeksieqznalazły się elementy mniejsze lub równe elementowi osiowemu (ang. pivot), natomiast za tym elementem – większe lub równe. W ten sposób otrzymamy jedną tablicę o wartościach nie większych oraz drugą o wartościach nie mniejszych odpivot.Zwyciężaj: dla powstałych w ten sposób dwóch podtablic wywołujemy rekurencyjnie funkcję sortowania szybkiego, która ponownie dzieli je na dwie podtablice i tak do momentu, aż uzyskamy tablice jednoelementowe.
Połącz: powstałe podtablice są zazwyczaj łączone w jedną, posortowaną całość. Jednak w przypadku sortowania szybkiego, będziemy wykonywać sortowanie w miejscu. Nie ma więc potrzeby łączenia elementów.
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/D7K12ECJ1
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.
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.
Słownik
algorytmy sortowania, w których elementy znajdują się cały czas w początkowej tablicy i nie jest potrzebna dodatkowa pamięć
element osiowy – element tablicy wybrany wedle ustalonego schematu; jest to element dzielący tablicę