Streszczenie Sortowanie szybkie (quicksort)
Sortowanie Szybkie (Quicksort): Algorytm, Złożoność, Pivot
Sortowanie Szybkie (Quicksort)
Sortowanie szybkie, powszechnie znane jako Quicksort, jest jednym z najbardziej efektywnych algorytmów sortowania porównawczego. Został opracowany przez Tony'ego Hoare'a w 1959 roku i do dziś pozostaje jednym z najczęściej używanych algorytmów sortowania w praktyce. Jego efektywność wynika z zastosowania paradygmatu „dziel i zwyciężaj”, który polega na rekurencyjnym dzieleniu problemu na mniejsze podproblemy, rozwiązywaniu ich niezależnie, a następnie łączeniu wyników.
Podstawowa Idea Algorytmu
Centralną koncepcją Quicksortu jest operacja partycjonowania (dzielenia). Algorytm działa w następujący sposób:
- Wybór pivota: Z listy elementów do posortowania wybierany jest jeden element, nazywany punktem obrotu lub pivotem. Jego wybór ma kluczowe znaczenie dla wydajności algorytmu.
- Partycjonowanie: Elementy listy są przestawiane w taki sposób, że wszystkie elementy mniejsze od pivota znajdują się po jego lewej stronie, a wszystkie elementy większe od pivota – po prawej. Elementy równe pivotowi mogą znaleźć się po dowolnej stronie. Po tej operacji pivot znajduje się na swojej ostatecznej pozycji w posortowanej liście.
- Rekurencja: Algorytm jest rekurencyjnie wywoływany dla podlisty elementów po lewej stronie pivota oraz dla podlisty elementów po prawej stronie pivota. Proces ten trwa, dopóki podlisty nie staną się jednoelementowe lub puste, co oznacza, że są już posortowane.
Pivot to element wybrany z listy, który służy jako punkt odniesienia podczas partycjonowania. Wszystkie elementy mniejsze od pivota są przenoszone na jedną stronę, a większe na drugą.
Wybór Pivota
Strategia wyboru pivota ma ogromny wpływ na wydajność Quicksortu, zwłaszcza w kontekście unikania najgorszego przypadku:
- Pierwszy/Ostatni element: Najprostszy wybór, ale prowadzi do gorszej wydajności dla już posortowanych lub odwrotnie posortowanych danych.
- Środkowy element: Lepszy niż pierwszy/ostatni, ale nadal podatny na specyficzne układy danych.
- Losowy pivot: Wybór pivota losowo z podlisty. Znacznie zmniejsza prawdopodobieństwo wystąpienia najgorszego przypadku, ponieważ jest mało prawdopodobne, aby losowy wybór konsekwentnie prowadził do złego podziału. W praktyce jest to często stosowana i skuteczna strategia.
- Mediana z trzech: Wybór mediany spośród trzech elementów (np. pierwszego, środkowego i ostatniego) podlisty. Ta strategia jest często używana, ponieważ zwiększa szanse na wybranie pivota, który dobrze dzieli listę, minimalizując ryzyko najgorszego przypadku.
Partycjonowanie Lomuto
Istnieje kilka schematów partycjonowania. Jednym z najprostszych do zrozumienia i zaimplementowania jest schemat Lomuto. W tym schemacie, zazwyczaj ostatni element podlisty jest wybierany jako pivot. Następnie lista jest skanowana, a elementy mniejsze lub równe pivotowi są przenoszone na początek podlisty. Oto kroki algorytmu partycjonowania Lomuto:
- Wybierz ostatni element podlisty jako pivot. (Można go zamienić miejscami z pierwszym elementem, aby uprościć pętlę, ale dla schematu Lomuto zazwyczaj pozostaje na końcu).
- Zainicjuj indeks $i$ na $początek_podlisty - 1$. Ten indeks będzie wskazywał na ostatni element, który jest mniejszy lub równy pivotowi.
- Przejdź przez podlistę od $początku_podlisty$ do $koniec_podlisty - 1$ (czyli do elementu przed pivotem) za pomocą indeksu $j$.
- Jeśli $element[j]$ jest mniejszy lub równy pivotowi: a. Zwiększ $i$ o $1$. b. Zamień miejscami $element[i]$ i $element[j]$.
- Po zakończeniu pętli, zamień miejscami $element[i + 1]$ i pivot (czyli $element[koniec_podlisty]$).
- Zwróć $i + 1$, czyli ostateczną pozycję pivota.
Przykład Pa
Zarejestruj się po pełne podsumowanieMasz już konto? Zaloguj się
Quicksort - Sortowanie Szybkie
Klíčová slova: Quicksort, Złożoność czasowa algorytmu
Klíčové pojmy: Quicksort to algorytm sortowania porównawczego oparty na paradygmacie „dziel i zwyciężaj”., Podstawą Quicksortu jest wybór **pivota** i operacja **partycjonowania**., Partycjonowanie przestawia elementy tak, że mniejsze są po lewej, a większe po prawej stronie pivota., Algorytm rekurencyjnie sortuje podlisty po obu stronach pivota., Wybór pivota (np. losowy, mediana z trzech) ma kluczowe znaczenie dla wydajności algorytmu., Schemat partycjonowania Lomuto zazwyczaj wybiera ostatni element jako pivot i przesuwa mniejsze elementy na początek., Quicksort nie jest algorytmem stabilnym, co oznacza, że kolejność równych elementów może się zmienić., Typowe błędy to niewłaściwy wybór pivota, błędy w implementacji partycjonowania oraz brak przypadku bazowego rekurencji., Interaktywne symulacje pomagają wizualizować kroki partycjonowania i ruch indeksów $i$ i $j$., Pseudokod Quicksort i partycjonowania Lomuto jasno definiuje strukturę algorytmu.