Sortowanie Shella (shellsort)

WPROWADZENIE

Jest to poprawione sortowanie przez wstawianie, sortowanie za pomocą malejących przyrostów. Na szybkość algorytmu wpływa wybór sekwencji przyrostów. Przykładowe sekwencje, które dają dobrą wydajność:

• 1, 4, 13, 40, 121, 364, 1093, 3280, ...
  a[1] = 1, a[n + 1] = 3 * a[n] + 1, czyli a[n] = (3^n - 1) / 2;
• 1, 8, 23, 77, 281, 1073, 4193, ...
  a[1] = 1, a[2] = 8, a[n] = 1 + 3 * 2^(n-2) + 4^(n - 1) dla n > 2.

# Wersja wg Kernighana i Ritchiego.
# Oryginalna sekwencja przyrostów Shella: 1, 2, 4, 8, 16, 32, ...
# Metoda degeneruje się do czasu kwadratowego dla złośliwych danych.

def shellsort(L, left, right):
    h = (right - left) // 2
    while h > 0:
        for i in range(left + h, right + 1):
            for j in range(i, left + h - 1, -h):
                if L[j - h] > L[j]:
                    swap(L, j - h, j)
        h = h // 2

# Wersja wg Sedgewicka.

def shellsort(L, left, right):
    # Ustalenie największego kroku z sekwencji:
    # 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, ...
    h = 1
    while h <= (right-left) // 9:
        h = 3*h+1
    while h > 0:
        for i in range(left+h, right+1):
            j = i
            # Zamiast swap() mamy przesuniecia.
            item = L[i]
            while j >= left+h and item < L[j-h]:
                L[j] = L[j-h]
                j = j-h
            L[j] = item
        h = h // 3