def selectionsort(L):
    for x in range(len(L)-1):
        minpos = x
        for y in range(x, len(L)):
            if L[y] < L[minpos]:
                minpos = y
        L[x], L[minpos] = L[minpos], L[x]
    return L


def insertionsort(list):
    for index in range(1, len(list)):
        value = list[index]
        i = index - 1

        while i>=0:
            if value < list[i]:
                list[i+1] = list[i]
                list[i] = value
                i = i - 1
            else:
                break
    return list





def bubblesort(sequenz):
    for x in range(len(sequenz)):
        for k in range(len(sequenz) - 1):
            if sequenz[k] > sequenz[k+1]:
                sequenz[k],sequenz[k+1] = sequenz[k+1],sequenz[k]
    return sequenz






def quicksort(links,rechts,liste):
        G=links
        k=rechts
        pivot=int((rechts+links)/2)
        while (not ((G==k)and(G==pivot)) ):
            while ((not liste[G]>liste[pivot]) and (G<pivot)):
                G+=1
            while ((not liste[k]<liste[pivot]) and (k>pivot)):
                k-=1
            if (G==pivot):
                pivot=k
            elif (k==pivot):
                pivot=G
            (liste[G],liste[k])=(liste[k],liste[G])

        if (pivot-links > 1):
            quicksort(links,pivot-1,liste)
        if (rechts-pivot > 1):
            quicksort(pivot+1,rechts,liste)
        return L




# Test
print("Selectionsort:")
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = selectionsort(L)
print(L)


print("Insertionsort:")
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = insertionsort(L)
print(L)


print("Bubblesort:")
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = bubblesort(L)
print(L)


print("Quicksort:")
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = quicksort(0,len(L)-1, L)
print(L)