Sortowanie przez wstawianie (insertsort)

WPROWADZENIE

Sortowanie przez wstawianie polega na wstawianiu nowych elementów we właściwe miejsce już uporządkowanego zbioru. Algorytm jest stabilny. W czasie pracy algorytmu lewa strona tablicy zawiera rosnącą część posortowaną, a prawa strona tablicy zawiera malejącą część nieposortowaną, z której pobieramy kolejne elementy.

# Wersja nieadaptacyjna z dwiema pętlami for.

def insertsort(L, left, right):
    for i in range(left+1, right+1):
        for j in range(i, left, -1):   # od prawej do lewej (bez left)
            if L[j-1] > L[j]:
                swap(L, j-1, j)   # zamiana sąsiadów

# Wersja nieadaptacyjna z pętlami for i while.

def insertsort(L, left, right):
    for i in range(left+1, right+1):
        j = i
        while j > left:
            if L[j-1] > L[j]:
                swap(L, j-1, j)
            j = j-1

Porównania: 1 + 2 + ... + (n-1) = n*(n-1)/2.

Przestawienia: 1 + 2 + ... + (n-1) = n*(n-1)/2.

ULEPSZENIA

Można dokonać wielu ulepszeń:

• Można przestać porównywać elementy, gdy natrafimy na liczbę mniejszą od sprawdzanej, ponieważ z lewej strony liczby są już posortowane.
• Zamiast warunku j > left (w drugiej pętli) można znaleźć najmniejszy element i ustawić go na początku tablicy (wartownik).
• Można poprawić przestawianie sąsiednich elementów [przesuwanie zamiast kolejnych swap()].

# Wersja z wartownikiem wg Sedgewicka.
# Ta wersja jest adaptacyjna.

def insertsort(L, left, right):
    for i in range(right, left, -1):   # ustawiam wartownika
        if L[i-1] > L[i]: 
            swap(L, i-1, i)
    for i in range(left+2, right+1):
        j = i
        item = L[i]
        while item < L[j-1]:   # robimy miejsce na item
            L[j] = L[j-1]
            j = j-1
        L[j] = item

# https://pl.wikibooks.org/wiki/Kody_%C5%BAr%C3%B3d%C5%82owe/Sortowanie_przez_wstawianie
# Poprawiony kod pythonowy. Nie ma swap() i wartownika.

def insertsort(L, left, right):
    for i in range(left+1, right+1):   # L[left] jest posortowany
        item = L[i]
        j = i
        while j > left and L[j-1] > item:
            L[j] = L[j-1]   # robimy miejsce na item
            j = j-1
        L[j] = item

WERSJA REKURENCYJNA

Sortowanie przez wstawianie używa podejścia inkrementacyjnego: sortuj L w zakresie od left do j-1, potem wstaw L[j] we właściwe miejsce, aby otrzymać L posortowane w zakresie od left do j.

# Wersja rekurencyjna.

def insertsort(L, left, right):
    if left < right:
        insertsort(L, left, right-1)
        item = L[right]
        j = right
        # Tu widać, że wartownik upraszcza warunek pętli.
        while j > left and item < L[j-1]:   # robimy miejsce na item
            L[j] = L[j-1]
            j = j-1
        L[j] = item