Proste metody sortowania

WPROWADZENIE

Dobrą miarą efektywności algorytmu sortowania jest liczba koniecznych porównań kluczy i liczba koniecznych przesunięć (przestawień) obiektów. Metody proste wymagają rzędu n^2 porównań, a metody zaawansowane rzędu n*log(n). Metody proste sortowania w miejscu:

• sortowanie przez wybór (selekcję),
• sortowanie przez wstawianie (umieszczanie),
• sortowanie przez zamianę (bąbelkowe).

Metody proste sortowania wybiera się w następujących sytuacjach:

• jeżeli program sortowania musi być uruchomiony niewielką liczbę razy,
• jeżeli liczba elementów przeznaczonych do sortowania nie jest duża (powiedzmy, mniej niż tysiąc),
• jeżeli mamy do czynienia ze specyficznymi zbiorami danych (dane prawie posortowane, zbiory z dużą liczbą duplikatów).

IMPLEMENTACJA

Przedstawione implementacje algorytmów sortowania będą maiały postać funkcji typu anysort(L, left, right), gdzie sortowane będą elemeny na liście L na pozycjach od left do right włącznie. Wykorzystywana jest pomocnicza funkcja swap(L, left, right), która zamienia miejscami elementy na pozycjach left i right.

def swap(L, left, right):
    """Zamiana miejscami dwóch elementów."""
    # L[left], L[right] = L[right], L[left]
    item = L[left]
    L[left] = L[right]
    L[right] = item

# Sedgewick korzysta z jeszcze jednej funkcji pomocniczej.

def compswap(L, left, right):
    """Zamiana miejscami dwóch elementów, jeżeli warunek jest spełniony."""
    if L[left] > L[right]:
        # L[left], L[right] = L[right], L[left]
        item = L[left]
        L[left] = L[right]
        L[right] = item

def anysort(L, left, right):
    """Sortowanie listy L w miejscu od left do right włącznie."""
    pass