====== Sortieralgorithmen in Python ======

==== Bubble-Sort Algorithmus ====
** Idee: ** Man vergleicht die ersten beiden Elemente. Wenn die Reihenfolge falsch ist, dann tauscht man sie. Danach wandert man eine Stelle nach rechts und vergleicht das zweite und das dritte Element und tauscht diese gegebenenfalls. Dies wiederholt man bis man am Ende der Liste angekommen ist. Danach beginnt man wieder von vorne und geht bis zum vorletzten Element (warum?). Dies wiederholt man n mal. 

<sxh python>
def bubbleSort(list1):
    for i in range(len(list1)-1,0,-1): #i läuft rückwärts
        for j in range(0,i,1):
            drawList(list1,0.01)
            if list1[j]>list1[j+1]:
                list1[j],list1[j+1] = list1[j+1],list1[j]

bubbleSort(zufallsListe)
</sxh>

==== Selection-Sort ====
**Idee:** Man sucht das kleinste Element und setzt es ganz nach links. Danach sucht man im Rest der Liste das kleinste Element und setzt es an die zweite Stelle etc.

<sxh python>
#===============================================================
# Selection-Sort (Children-Sort)
#===============================================================

def getSmallestIndex(Liste1):
    smallestElement = Liste1[0]
    smallestIndex = 0
    for i in range(len(Liste1)):
        if Liste1[i] < smallestElement:
            smallestElement = Liste1[i]
            smallestIndex = i
    return smallestIndex
    
def selectionSort(Liste1):
    for i in range(len(Liste1)): 
        drawList(Liste1,0.1)
        index = getSmallestIndex(Liste1[i:]) + i 
        Liste1[i],Liste1[index] = Liste1[index],Liste1[i]
</sxh>

==== Swap-Sort ====
<sxh python>
def nAreSmaller(list1, n):
    howMany = 0
    for i in list1:
        if (i<n):
            howMany = howMany + 1
    return howMany

def swapSort(list1):
    index = 0
    while index<len(list1):
        drawList(list1,0.1)
        element = list1[index]
        nSmaller = nAreSmaller(list1,element)
        list1[index],list1[nSmaller] = list1[nSmaller],list1[index]
        if (index == nSmaller):
            index = index + 1
</sxh>

==== Merge-Sort ====
<sxh python>
def merge(l1,l2):
    c = []
    while len(l1) != 0 and len(l2) != 0:
        if l1[0] < l2[0]:
            c.append(l1[0])
            l1.remove(l1[0])
        else:
            c.append(l2[0])
            l2.remove(l2[0])
    if len(l1) == 0:
        c += l2
    else:
        c += l1
    return c

def mergesort(list1):
    if len(list1) == 0 or len(list1) == 1:
        return list1
    else:
        middle = int(len(list1)/2)
        a = mergesort(list1[:middle])
        b = mergesort(list1[middle:])
        return merge(a,b)
</sxh>