Sortowanie przez wstrząsanie (shakersort)

WPROWADZENIE

W sortowaniu przez wstrząsanie (inaczej: algorytm koktajlowy) przechodzimy przez dane na przemian: raz z lewa na prawo, raz z prawa na lewo. Jest to ulepszony algorytm sortowania bąbelkowego.

# Wersja na podstawie Wróblewskiego.
def shakersort(L, left, right):
    k = right
    while left < right:
        for j in range(right, left, -1):   # od prawej
            if L[j-1] > L[j]:
                swap(L, j-1, j)
                k = j
        left = k
        for j in range(left, right):   # od lewej
            if L[j] > L[j+1]:
                swap(L, j, j+1)
                k = j
        right = k