Twoje Centrum Szkoleniowe

C++: Sortowanie szybkie (Quick Sort)

Historia sortowania szybkiego sięga lat 60-tych XX wieku i jest związana z brytyjskim informatykiem Tony Hoare, który opracował ten algorytm w 1960 roku. Hoare wprowadził koncepcję dzielenia tablicy na mniejsze segmenty, co pozwalało na szybkie i efektywne sortowanie dużych zbiorów danych.

Charakterystyczną cechą sortowania szybkiego jest jego podejście podziału i zdobywania, znane jako divide and conquer. Algorytm wybiera element osiowy, zwany pivotem, a następnie porządkuje pozostałe elementy wokół tego pivotu, tak aby elementy mniejsze niż pivot znalazły się po jego lewej stronie, a większe po prawej. Następnie proces jest rekurencyjnie powtarzany dla mniejszych segmentów.

Sortowanie szybkie jest cenione za swoją szybkość i efektywność, szczególnie w przypadkach, gdy mamy do czynienia z dużymi zbiorami danych. Jego zdolność do szybkiego sortowania dużych tablic sprawia, że jest on często stosowany w różnorodnych aplikacjach, od systemów baz danych po algorytmy wyszukiwania i analizy danych.

 

Zasada działania sortowania szybkiego

 

Podział tablicy na podtablice

Podstawą działania sortowania szybkiego jest podział tablicy na mniejsze segmenty, nazywane podtablicami. Algorytm rozpoczyna się od wybrania elementu osiowego, zwanego pivotem. Pivot może być wybrany na różne sposoby, na przykład jako środkowy element tablicy, co jest częstą praktyką. Następnie algorytm porównuje pozostałe elementy tablicy z pivotem i przemieszcza je w taki sposób, aby wszystkie elementy mniejsze od pivotu znalazły się po jego lewej stronie, a wszystkie większe po prawej.

 

Proces wybierania elementu osiowego

Wybór odpowiedniego pivotu jest ważnym elementem, który wpływa na efektywność sortowania. Nieodpowiednio wybrany pivot może prowadzić do niezbalansowanego podziału tablicy, co negatywnie wpływa na wydajność algorytmu. Po wybraniu pivotu i przeprowadzeniu pierwszego podziału, proces jest rekurencyjnie powtarzany dla każdej z utworzonych podtablic.

 

Rekurencyjny charakter algorytmu

Po podziale początkowej tablicy na mniejsze segmenty, sortowanie szybkie stosuje ten sam proces rekurencyjnie do każdej z podtablic. Proces ten jest kontynuowany do momentu, gdy każda podtablica składa się z jednego lub żadnego elementu, co oznacza, że tablica jest w pełni posortowana. Rekurencja jest naturalnym wyborem dla tego typu algorytmów, ponieważ pozwala na łatwe i efektywne dzielenie problemu sortowania na mniejsze, bardziej zarządzalne części.

 

Przykładowa implementacja sortowania szybkiego w C++

 

Kroki Implementacji sortowania szybkiego

1. Wybór pivotu: Pierwszym krokiem jest wybór elementu osiowego. Istnieje wiele strategii wyboru pivotu, ale najczęściej wybiera się środkowy element, pierwszy element lub losowy element tablicy. Wybór ten ma znaczący wpływ na wydajność algorytmu.

2. Podział tablicy: Następnie algorytm porównuje każdy element tablicy z pivotem, przemieszczając elementy mniejsze od pivotu na lewo, a większe na prawo. Dzięki temu pivot znajdzie się na swojej ostatecznej pozycji w posortowanej tablicy.

3. Rekurencyjne sortowanie: Po podzieleniu tablicy na dwie części (elementy mniejsze i większe od pivotu), algorytm rekurencyjnie powtarza proces sortowania dla każdej z tych części.

4. Zakończenie rekurencji: Rekurencja kończy się, gdy algorytm osiągnie podtablice składające się z jednego lub żadnego elementu, co oznacza, że są one już posortowane.

 

Wersja rekurencyjna

#include <iostream>
using namespace std;

void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

 

Analiza kodu

• Wybór pivotu: int pivot = arr[(left + right) / 2]; - pivot jest wybrany jako środkowy element podtablicy.

• Podział tablicy: Pętla while (i <= j) służy do przemieszczenia elementów mniejszych i większych od pivotu odpowiednio na lewą i prawą stronę.

• Rekurencja: Funkcja quickSort jest wywoływana rekurencyjnie dla dwóch części tablicy - quickSort(arr, left, j) i quickSort(arr, i, right).

• Warunki końca rekurencji: Warunki if (left < j) i if (i < right) zapewniają, że rekurencja kończy się, gdy nie ma już co sortować.

 

 

Wersja iteracyjna

#include <iostream>
#include <stack>
using namespace std;

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void quickSortIterative(int arr[], int l, int h) {
    stack<int> stack;
    stack.push(l);
    stack.push(h);

    while (!stack.empty()) {
        h = stack.top();
        stack.pop();
        l = stack.top();
        stack.pop();

        int pivot = arr[h];
        int i = l - 1;

        for (int j = l; j <= h - 1; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[h]);

        int p = i + 1;

        if (p - 1 > l) {
            stack.push(l);
            stack.push(p - 1);
        }
        if (p + 1 < h) {
            stack.push(p + 1);
            stack.push(h);
        }
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSortIterative(arr, 0, n - 1);

    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

 

Analiza Kodu

 

1. Inicjalizacja Stosu:

   • stack<int> stack; tworzy stos przechowujący indeksy podtablic, które mają zostać posortowane.

2. Pętla Główna:

   • while (!stack.empty()) kontynuuje działanie, dopóki stos nie zostanie opróżniony.

3. Obsługa Stosu:

   • h = stack.top(); stack.pop(); pobiera górny element ze stosu jako indeks prawego końca podtablicy.
   • l = stack.top(); stack.pop(); analogicznie dla lewego końca.

4. Wybór Pivotu i Partycjonowanie:

   • int pivot = arr[h]; wybiera ostatni element podtablicy jako pivot.
   • Pętla for przechodzi przez elementy podtablicy, porównując je z pivotem i przesuwając mniejsze elementy na lewo.

5. Zamiana Pivotu:

   • swap(arr[i + 1], arr[h]); umieszcza pivot w odpowiedniej pozycji.

6. Dodawanie Nowych Podtablic do Stosu:

   • Warunki if sprawdzają, czy istnieją elementy po lewej lub prawej stronie pivotu i dodają ich indeksy do stosu.

7. Wydruk Posortowanej Tablicy:

   • Pętla for w main wyświetla posortowaną tablicę.

 

Iteracyjna wersja algorytmu sortowania szybkiego jest bardziej złożona niż rekurencyjna, ale eliminuje ryzyko przekroczenia limitu stosu rekurencyjnego, co jest ważne przy bardzo dużych danych. Wydajność czasowa algorytmu pozostaje zbliżona do rekurencyjnej wersji.

 

 

Optymalizacje i Warianty Algorytmu Sortowania Szybkiego

 

Techniki Optymalizacji

1. Wybór lepszego pivotu: Jedną z kluczowych technik optymalizacji jest poprawa metody wyboru elementu osiowego (pivot). Wybór pivotu ma istotny wpływ na liczbę potrzebnych podziałów tablicy. Ulepszenia mogą obejmować na przykład wybór mediany z pierwszego, środkowego i ostatniego elementu tablicy, co zazwyczaj zapewnia lepszy podział niż wybór losowego lub stałego elementu.

2. Iteracyjne podejście: Inną techniką jest zastąpienie rekurencji iteracją, co może pomóc zmniejszyć zużycie pamięci stosu, szczególnie w przypadku dużych zbiorów danych.

3. Ograniczenie głębokości rekurencji: Ograniczenie głębokości rekurencji do logarytmicznej zależności od rozmiaru tablicy może zapobiegać scenariuszom najgorszego przypadku, gdzie algorytm mógłby stać się nieefektywny.

Warianty Algorytmu

1. Sortowanie trójdrożne (3-way Quick Sort): Ten wariant sortowania szybkiego jest szczególnie użyteczny w przypadku tablic zawierających wiele powtarzających się elementów. W sortowaniu trójdrożnym, oprócz podziału tablicy na części mniejsze i większe od pivotu, tworzy się także sekcję z elementami równymi pivotowi. Pozwala to uniknąć niepotrzebnego porównywania elementów równych ze sobą.

2. Hybrydowe sortowanie: Kolejnym podejściem jest połączenie sortowania szybkiego z innymi algorytmami sortowania, takimi jak sortowanie przez wstawianie, w celu optymalizacji dla mniejszych podtablic. Takie hybrydowe metody mogą oferować lepszą wydajność, szczególnie dla małych zbiorów danych lub danych częściowo posortowanych.

 

 

Analiza Złożoności Sortowania Szybkiego

 

Złożoność Czasowa Algorytmu

1. Najlepszy Przypadek: W idealnych warunkach, kiedy pivot (element osiowy) jest wybierany tak, aby równomiernie dzielił tablicę na podtablice, złożoność czasowa sortowania szybkiego wynosi O(n log n). Oznacza to, że czas działania algorytmu wzrasta logarytmicznie w stosunku do wzrostu liczby elementów do posortowania.

2. Średni Przypadek: W typowych, losowo rozłożonych zbiorach danych, sortowanie szybkie również osiąga złożoność O(n log n), co sprawia, że jest jednym z najszybszych algorytmów sortowania dostępnych dla ogólnego użytku.

3. Najgorszy Przypadek: Najgorszy przypadek występuje, gdy każdy wybór pivotu prowadzi do podziału, w którym jedna podtablica zawiera wszystkie elementy oprócz pivotu. W takiej sytuacji złożoność algorytmu wzrasta do O(n²). Może to mieć miejsce, na przykład, gdy tablica jest już posortowana, a pivot jest zawsze wybierany jako pierwszy lub ostatni element. Jednakże, w praktyce, taka sytuacja zdarza się rzadko, zwłaszcza gdy stosuje się odpowiednie metody wyboru pivotu.