Quicksort

Tutorial
Na ten temat mamy również tutorial „Quicksort”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
Quicksort (1) Przykładowe wykonanie algorytmu quicksort
Quicksort przerzucanie (2) Przykładowe wykonanie operacji przerzucania elementów wokół klucza osiowego
REKLAMA Algorytmy. Ćwiczenia
34,90 zł
Czysty kod. Podręcznik dobrego programisty
69,00 zł
Vue.js 2. Wprowadzenie dla profesjonalistów
−30%69,30 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł

Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.

Przebieg algorytmu

Quicksort jest algorytmem rekurencyjnym, jego działanie można opisać następująco:

  • Wybierz jeden z elementów jako klucz osiowy,
  • Przenieś wszystkie elementy mniejsze od klucza osiowego na jedną stronę tablicy, a pozostałe na drugą,
  • Wywołaj procedurę rekurencyjnie dla części tablicy na lewo od klucza osiowego i na prawo od klucza osiowego.

Wybór klucza osiowego może być dowolny, jednak powinien być jak najszybszy. W praktyce często stosuje się po prostu wybór pierwszego elementu.

Operacja przerzucania elementów powinna musi być zaimplementowana tak, aby wykonywała się w czasie liniowym. Przykładowo, może ona być zdefiniowana w następujący sposób:

  • Przyjmujemy pierwszy element za klucz osiowy.
  • Dla każdego kolejnego elementu:
    • Jeśli jest większy od klucza osiowego, zostawiamy go na miejscu.
    • W przeciwnym razie zamieniamy go miejscami z pierwszym elementem większym od klucza osiowego (wyjątek: jeśli nie znaleźliśmy wcześniej żadnego elementu większego od klucza osiowego, nie robimy nic).
  • Zamieniamy miejscami klucz osiowy z ostatnim elementem mniejszym od niego.

Analiza algorytmu

Jak już wspomniano, operacja przenoszenia elementów odbywa się w czasie liniowym. O złożoności algorytmu decyduje więc to, ile nastąpi rekurencyjnych wywołań funkcji. W przypadku optymistycznym tablica będzie dzielona na pół. Wówczas głębokość drzewa wywołań zależy logarytmicznie od liczby danych wejściowych, czyli optymistyczna złożoność czasowa algorytmu jest rzędu O(n logn). Możemy wykazać, że taki sam rząd złożoności wystąpi w przypadku średnim (dowód jest dostępny w książkach podanych w bibliografii).

Przypadek pesymistyczny występuje wtedy, gdy klucz osiowy za każdym razem znajdzie się na brzegu tabeli. Wówczas przy każdym kolejnym wywołaniu liczba elementów do posortowania jest tylko o 1 mniejsza, zatem funkcja zostanie wywołana n razy. Pesymistyczna złożoność czasowa wynosi zatem O(n2).

Przeanalizujmy złożoność pamięciową algorytmu. Sortowanie szybkie nie potrzebuje co prawda dodatkowej pamięci na przechowywanie sortowanych danych, wymaga jednak pamięci potrzebnej na obsługę rekurencyjnych wywołań funkcji. Rozmiar tej pamięci (podobnie jak czas wykonania) będzie zależał od głębokości drzewa wywołań. Złożoność pamięciowa wynosi więc O(logn) w przypadku średnim i O(n) w przypadku pesymistycznym. Nie jest to zatem algorytm sortujący w miejscu.

Zastanówmy się, kiedy może wystąpić przypadek pesymistyczny. Jeśli jako klucz osiowy obieramy pierwszy (lub ostatni) elementu z tablicy, to najgorszy przypadek wystąpi wtedy, gdy tablica jest już posortowana. Widzimy więc, że algorytm zachowuje się w sposób bardzo nienaturalny.

Możliwe usprawnienia

Niedoskonałości algorytmu można nieco poprawić stosując następujące techniki:

  • Jako klucz osiowy zamiast pierwszego elementu można obierać element losowy. Nie zmieni to złożoności algorytmu, jednak sprawi, że przypadek pesymistyczny nie będzie występował w przypadku tablicy posortowanej.
  • Przy wyborze klucza osiowego można zastosować nieco bardziej złożone techniki. Jednym z rozwiązań jest wybór mediany z kilku wybranych elementów (np. pierwszego, ostatniego i środkowego). Należy jednak uważać, żeby nie spowolniło to zbytnio całej procedury – siła omawianego algorytmu tkwi w tym, aby wybór klucza osiowego i przestawianie elementów było jak najszybsze.
  • W celu zmniejszenia liczby rekurencyjnych wywołań funkcji, dla małych tablic można zastosować jakiś prosty, nierekurencyjny algorytm sortowania, np. sortowanie przez wstawianie (wówczas mamy do czynienia z algorytmem hybrydowym).
  • Jeśli wartość klucza osiowego powtarza się w tablicy, można od razu ustawić te elementy obok klucza osiowego i nie włączać tego fragmentu tablicy do wywołań rekurencyjnych. Taka modyfikacja jest określana jako Quick Sort 3 Way Partition.

Kod źródłowy

Przykładowa implementacja algorytmu w języku C wygląda następująco:

void quicksort(int* tab, int poczatek, int n)
{
    if (n > 1) 
    {
        int liczba_mniejszych = 0;
        int liczba_wiekszych = 0;
        
        int koniec = poczatek + n;
        int t; // Zmienna tymczasowa
    
        // Przeniesienie elementow wokol klucza osiowego
        for (int i = (poczatek + 1); i < koniec; ++i)
        {
            
            if (tab[i] < tab[poczatek])
            {   
                if (liczba_wiekszych > 0)
                {
                    // Przeniesienie elementu mniejszego od klucza osiowego
                    // przed elementy wieksze od klucza osiowego
                    t = tab[poczatek+liczba_mniejszych+1];
                    tab[poczatek+liczba_mniejszych+1] = tab[i];
                    tab[i] = t;
                }                    
                ++liczba_mniejszych; 
            }
            else
            {
                ++liczba_wiekszych;
            }
            
        }
        
        // Wstawienie klucza osiowego na wlasciwe miejsce
        t = tab[poczatek+liczba_mniejszych];
        tab[poczatek+liczba_mniejszych] = tab[poczatek];
        tab[poczatek] = t;
        
        // Wywołanie rekurencyjne
        quicksort(tab, poczatek, liczba_mniejszych);
        quicksort(tab, koniec-liczba_wiekszych, liczba_wiekszych);
        
    }
}

// Przykladowe uzycie funkcji
int main()
{
    int tab[] = {3, 7, 5, 1, 5, 8, 4, 2};
    quicksort(tab, 0, 8);
    
    return 0; 
}

Bibliografia

Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 5 stycznia 2018 18:56, ostatnia edycja: 13 lutego 2019 16:40.

REKLAMA

Zobacz też

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość

Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.

→ Czytaj całość

Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

→ Czytaj całość
Polityka prywatnościKontakt