Sortowanie przez wybór (selectsort)

WPROWADZENIE

Sortowanie przez wybór działa na zasadzie ciągłego wybierania najmniejszego elementu z coraz mniejszego zbioru danych. Algorytm jest niestabilny [b1,b2,a,c]. Wada algorytmu: czas jego działania prawie nie zależy od stopnia uporządkowania ciągu.

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

Przestawienia: (n-1) [bardzo mało].

def selectsort(L, left, right):
    for i in range(left, right):
        k = i
        for j in range(i+1, right+1):
            if L[j] < L[k]:
                k = j
        swap(L, i, k)

WERSJA STABILNA

Zwiększając liczbę przestawień możemy otrzymać stabilną wersję sortowania przez wybór.

def selectsort(L, left, right):
    for i in range(left, right):
        k = i
        for j in range(i+1, right+1):
            if L[j] < L[k]:
                k = j
        item = L[k]
        while k > i:
            L[k] = L[k-1]
            k = k-1
        L[i] = item

WERSJA REKURENCYJNA

Sortowanie przez wybór ma strukturę rekurencyjną: ustaw najmniejszy element na pozycji left, sortuj L w zakresie od left+1 do right.

def selectsort(L, left, right):
    if left < right:
        k = left
        for j in range(left+1, right+1):
            if L[j] < L[k]:
                k = j
        item = L[k]
        while k > left:
            L[k] = L[k-1]
            k = k-1
        L[left] = item
        selectsort(L, left+1, right)