Szybkie sortowanie Quick Sort

Quick Sort, czyli szybkie sortowanie (quicksort), to jeden z najpopularniejszych algorytmów sortowania. Jego popularność wynika z wysokiej wydajności i względnej prostoty implementacji. Poniżej znajduje się szczegółowy opis tego algorytmu, jego zalet i wad oraz bardziej zaawansowana implementacja w języku Python.

Jak działa quicksort?

1. Wybierz element z tablicy jako pivot. Wybór pivota może być dokonany na kilka sposobów, może to być:

  • pierwszy element tablicy,
  • ostatni element tablicy,
  • losowy element tablicy,
  • mediana z trzech elementów (np. pierwszy, środkowy, ostatni).

2. Przearanżuj tablicę w taki sposób, aby wszystkie elementy mniejsze od pivota znalazły się po jego lewej stronie, a wszystkie elementy większe od pivota po jego prawej stronie. Pivot znajdzie się wtedy na swojej ostatecznej pozycji.

3. Rekurencyjnie zastosuj quicksort do podtablic utworzonych przez podział oryginalnej tablicy wokół pivota.

Implementacje quicksort w języku Python

Standardowa implementacja algorytmu algorytmu quicksort

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quicksort(left) + middle + quicksort(right)
# Przykład użycia
arr = [3, 6, 8, 10, 1, 2, 1]
print("Nieposortowana tablica:", arr)
sorted_arr = quicksort(arr)
print("Posortowana tablica:", sorted_arr)

Analiza działania powyższego algorytmu

Funkcja quicksort

  1. sprawdza, czy długość tablicy jest mniejsza lub równa 1. Jeśli tak, zwraca tablicę (jest już posortowana),
  2. wybiera pivot jako środkowy element tablicy.
  3. tworzy trzy listy: left (elementy mniejsze od pivota), middle (elementy równe pivotowi) oraz right (elementy większe od pivota),
  4. rekurencyjnie sortuje listy left i right i łączy je z middle w celu uzyskania posortowanej tablicy.

Bardziej zaawansowana implementacja algorytmu quicksort w języku Python, wykorzystująca metodę partycjonowania Lomuto

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
# Przykład użycia
arr = [3, 6, 8, 10, 1, 2, 1]
n = len(arr)
print("Nieposortowana tablica:", arr)
quicksort(arr, 0, n-1)
print("Posortowana tablica:", arr)

Metoda partycjonowania Lomuto

  • W tej metodzie pivotem jest zazwyczaj ostatni element tablicy.
  • Używamy dwóch wskaźników i (indeks większego elementu) i j (bieżący indeks). Wskaźnik i zaczyna się przed pierwszym elementem tablicy (low - 1), a j przechodzi przez każdy element od low do high - 1.
  • Dla każdego elementu od low do high - 1, jeśli element jest mniejszy lub równy pivotowi, zwiększamy i i zamieniamy elementy arr[i] i arr[j].
  • Po przejściu przez wszystkie elementy, zamieniamy element arr[i + 1] z pivotem (arr[high]), aby pivot znalazł się na właściwej pozycji.

Złożoność obliczeniowa quicksort

Średnia złożoność czasowa dla większości przypadków jest równa O(n log n)
Najgorsza złożoność czasowa wynosi O(n2), gdy pivot zawsze dzieli tablicę na bardzo nierówne części (np. gdy tablica jest już posortowana i zawsze wybieramy pierwszy lub ostatni element jako pivot).
Złożoność pamięciowa wynosi O(log ⁡n) - wykorzystanie pamięci na stos rekurencyjny.

Zalety i wady quicksort

Zalety

  • Jest szybszy w praktyce dla dużych tablic w porównaniu do innych algorytmów sortowania, takimi jak sortowanie bąbelkowe czy sortowanie przez wstawianie.
  • Jest bardzo efektywny dla dużych zbiorów danych.
  • Działa in-place, tzn. nie wymaga dodatkowej pamięci na przechowywanie danych.

Wady

  • W niektórych przypadkach może wystąpić złożoność czasowa O(n2).
  • Algorytm jest niestabilny, co oznacza, że nie zachowuje oryginalnej kolejności równych elementów.

Metody optymalizacji algorytmu quicksort

  1. Randomized Quick Sort - wybieranie pivota losowo, aby zredukować ryzyko najgorszego przypadku.
  2. Dual Pivot Quick Sort - używanie dwóch pivotów zamiast jednego.
  3. Introsort - łączy quicksort z heapsortem, aby zagwarantować najgorszą złożoność czasową O(n log n).

Quick Sort jest potężnym algorytmem sortowania, który jest szeroko stosowany ze względu na swoją wydajność i wszechstronność. Jednakże, jak każdy algorytm, ma swoje zalety i wady, które należy rozważyć przed jego zastosowaniem.

Komentarze