Sortowanie szybkie (quicksort)

WPROWADZENIE

Sortowanie szybkie to poprawiony algorytm sortowania bąbelkowego. Podstawowa wersja algorytmu została wynaleziona w 1960 roku przez Hoare'a i od tego czasu był intensywnie badany. Stosowana jest zasada dziel i zwyciężaj. Algorytm jest klasy O(n log n) w typowych sytuacjach, oraz O(n^2) w najgorszym przypadku. Jako element podziału wybiera się element: środkowy, pierwszy, ostatni, losowy, medianę, medianę z trzech (chodzi o zapobieganie niekorzystnym przypadkom). Element podziału trafia od razu na swoje miejsce. Algorytm jest niestabilny.

# Wersja wg Kernighana i Ritchiego.

def quicksort(L, left, right):
    if left >= right:
        return
    swap(L, left, (left + right) // 2)   # element podziału
    pivot = left                      # przesuń do L[left]
    for i in range(left + 1, right + 1):   # podział
        if L[i] < L[left]:
            pivot += 1
            swap(L, pivot, i)
    swap(L, left, pivot)     # odtwórz element podziału
    quicksort(L, left, pivot - 1)
    quicksort(L, pivot + 1, right)

# Wersja wg Cormena.

def quicksort(L, left, right):
    """Sortowanie szybkie wg Cormena str. 169."""
    if left >= right:
        return
    pivot = partition(L, left, right)
    # pivot jest na swoim miejscu.
    quicksort(L, left, pivot - 1)
    quicksort(L, pivot + 1, right)

def partition(L, left, right):
    """Zwraca indeks elementu rozdzielającego."""
    # Element rozdzielający to ostatni z prawej,
    # dlatego na końcu trzeba go przerzucić do środka.
    # Będzie on na docelowej pozycji ze względu na sortowanie.
    x = L[right]   # element rozdzielający
    i = left
    for j in range(left, right):
        if L[j] <= x:
            swap(L, i, j)
            i += 1
    swap(L, i, right)
    return i

Algorytm można przyspieszyć wywołując dla małych ciągów inną metodę sortowania, np. insertsort().

# Typowo m wynosi między 5 a 25.
if (right - left) <= m:
    insertsort(L, left, right)

Następna wersja quicksort().

# https://pl.wikibooks.org/wiki/Kody_%C5%BAr%C3%B3d%C5%82owe/Sortowanie_szybkie#Python

def quicksort(L, left, right):
    i = left
    j = right
    pivot = L[(left + right) // 2]   # element srodkowy
    while i <= j:   # w koncu i przeskoczy j
        while L[i] < pivot:
            i += 1   # dojdzie najwyzej do pivot z lewej
        while pivot < L[j]:
            j -= 1    # dojdzie najwyzej do pivot z prawej
        if i <= j:   # w koncu i przeskoczy j
            swap(L, i, j)
            i += 1
            j -= 1
    if left < j:
        quicksort(L, left, j)
    if i < right:
        quicksort(L, i, right)