Szybkie sortowanie

9.1 Definicja szybkiego sortowania

Szybkie sortowanie (Quick Sort) — to efektywny algorytm sortowania, który używa podejścia "dziel i rządź". Działa przez wybór elementu odniesienia (pivot), podział tablicy na dwa podtablice — elementy mniejsze od odniesienia i elementy większe od odniesienia, a następnie rekursywne zastosowanie tego samego procesu do każdego podtablicy.

Algorytm szybkiego sortowania powstał jako próba rozwiązania problemu „jak najszybciej przemieścić małe elementy w lewo, a duże w prawo”. Załóżmy, że mamy najmniejszy element — skrajnie z prawej, czy można go jakoś szybko przemieścić, jeśli nie na jego finalną pozycję, to blisko niej? To by znacznie zmniejszyło liczbę niepotrzebnych porównań.

Zasada działania:

1. Wybór elementu odniesienia (pivot):

Wybieramy element z tablicy jako odniesienie. Może to być pierwszy element, ostatni element, środkowy element lub losowy element. Czasami to jest średnia arytmetyczna trzech losowych elementów.

2. Podział (partitioning):

Przenosimy wszystkie elementy mniejsze od odniesienia na lewą stronę tablicy, a wszystkie elementy większe od odniesienia — na prawą stronę. W wyniku tego element odniesienia znajduje się na swoim ostatecznym miejscu w posortowanej tablicy.

3. Rekursywne zastosowanie:

Rekursywnie stosujemy proces do lewego i prawego podtablicy, nie włączając elementu odniesienia.

Krok po kroku

1. Wybieramy element odniesienia.
2. Przenosimy elementy mniejsze od odniesienia na lewo, a elementy większe — na prawo.
3. Rekursywnie stosujemy proces do podtablic.

Czasowa i przestrzenna złożoność szybkiego sortowania

Złożoność czasowa:

• W najgorszym przypadku: O(n^2) — zdarza się, gdy za każdym razem wybierany jest najgorszy element odniesienia (na przykład, gdy tablica jest już posortowana).
• W przypadku średnim: O(n log n) — dla losowo rozłożonych danych.
• W najlepszym przypadku: O(n log n) — gdy tablica za każdym razem dzieli się na równe części.

Złożoność przestrzenna:

O(log n) — jest potrzebna do przechowywania stosu wywołań rekursji, jeśli używana jest rekursja ogonowa i elementy odniesienia są wybierane pomyślnie.

9.2 Implementacja algorytmu szybkiego sortowania

Implementacja w Pythonie:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Podstawowy przypadek: tablica z 0 lub 1 elementem już jest posortowana
    
    pivot = arr[len(arr) // 2]  # Wybieramy element odniesienia
    left = [x for x in arr if x < pivot]  # Elementy mniejsze od odniesienia
    middle = [x for x in arr if x == pivot]  # Elementy równe odniesieniu
    right = [x for x in arr if x > pivot]  # Elementy większe od odniesienia
    
    return quick_sort(left) + middle + quick_sort(right)

# Przykład użycia:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Posortowana tablica:", sorted_arr)
# Wyjście: Posortowana tablica: [1, 1, 2, 3, 6, 8, 10]

Przykład działania algorytmu

Weźmy przykład tablicy: [3, 6, 8, 10, 1, 2, 1]

Pierwsze przejście:

• Element odniesienia: 8
• Elementy lewe: [3, 6, 1, 2, 1]
• Elementy środkowe: [8]
• Elementy prawe: [10]

Rekursywne sortowanie lewej części [3, 6, 1, 2, 1]:

• Element odniesienia: 1
• Elementy lewe: []
• Elementy środkowe: [1, 1]
• Elementy prawe: [3, 6, 2]

Rekursywne sortowanie prawej części [3, 6, 2]:

• Element odniesienia: 6
• Elementy lewe: [3, 2]
• Elementy środkowe: [6]
• Elementy prawe: []

Rekursywne sortowanie lewej części [3, 2]:

• Element odniesienia: 2
• Elementy lewe: []
• Elementy środkowe: [2]
• Elementy prawe: [3]

Wynik scalania: [1, 1, 2, 3, 6] dla lewej części, [10] dla prawej części, i [8] dla środkowej.

Końcowa posortowana tablica: [1, 1, 2, 3, 6, 8, 10]