====== Sortieralgorithmen ======

===== Minsort =====

Eine Liste von Zahlen wird von links nach rechts durchgegangen. Falls es rechts von dem aktuellen Element noch ein kleineres Element gibt, so wird das aktuelle Element mit dem kleinsten Element rechts von ihm ausgetauscht.

<code Python>
def minsort(liste):

    # gehe die Liste von Anfang bis zur vorletzen Stelle durch (Zähler i)
    for i in range(len(liste)-1):

        # suche das Minimum von der i-ten Stelle bis zum Ende
        minimum = i
        for z in range(i, len(liste)):
            if liste[z] < liste[minimum]:
                minimum = z

        # Tausche i-te Stelle mit dem Minimum, falls sie sich unterscheiden
        if minimum != i:
            print"Tausche %d. Element (%d) mit %d. Element (%d)"%(i+1, liste[i], minimum+1, liste[minimum])
            tausch = liste[minimum]
            liste[minimum] = liste[i]
            liste[i] = tausch

    return liste
</code>

Testen von der Python-Shell aus:

<code>
>>> minsort([10,11,12,13])
[10, 11, 12, 13]
>>> minsort([13,12,11,10])
Tausche 1. Element (13) mit 4. Element (10)
Tausche 2. Element (12) mit 3. Element (11)
[10, 11, 12, 13]
>>> minsort([13,12,10,11])
Tausche 1. Element (13) mit 3. Element (10)
Tausche 2. Element (12) mit 4. Element (11)
Tausche 3. Element (13) mit 4. Element (12)
[10, 11, 12, 13]
</code>

===== Quicksort =====

...wenn das nicht genial ist...  Lässt man die Zwischenausgaben weg, dann ist es ein 7-Zeiler!

<code Python>
def quicksort(liste):
    print "Sortiere",liste
    if len(liste) <= 1:
        print "nichts zu tun!"
        return liste
    pivotelement = liste[0]
    links  = [element for element in liste[1:] if element <  pivotelement]
    rechts = [element for element in liste[1:] if element >= pivotelement]
    print "Linker Teil:",links,"Pivotelement:",pivotelement,"Rechter Teil:",rechts
    return quicksort(links) + [pivotelement] + quicksort(rechts)
</code>

Ein Probelauf von der Shell aus:

<code>
>>> quicksort([3,16,8,2,1,14,9,20,13,0,18])
Sortiere [3, 16, 8, 2, 1, 14, 9, 20, 13, 0, 18]
Linker Teil: [2, 1, 0] Pivotelement: 3 Rechter Teil: [16, 8, 14, 9, 20, 13, 18]
Sortiere [2, 1, 0]
Linker Teil: [1, 0] Pivotelement: 2 Rechter Teil: []
Sortiere [1, 0]
Linker Teil: [0] Pivotelement: 1 Rechter Teil: []
Sortiere [0]
nichts zu tun!
Sortiere []
nichts zu tun!
Sortiere []
nichts zu tun!
Sortiere [16, 8, 14, 9, 20, 13, 18]
Linker Teil: [8, 14, 9, 13] Pivotelement: 16 Rechter Teil: [20, 18]
Sortiere [8, 14, 9, 13]
Linker Teil: [] Pivotelement: 8 Rechter Teil: [14, 9, 13]
Sortiere []
nichts zu tun!
Sortiere [14, 9, 13]
Linker Teil: [9, 13] Pivotelement: 14 Rechter Teil: []
Sortiere [9, 13]
Linker Teil: [] Pivotelement: 9 Rechter Teil: [13]
Sortiere []
nichts zu tun!
Sortiere [13]
nichts zu tun!
Sortiere []
nichts zu tun!
Sortiere [20, 18]
Linker Teil: [18] Pivotelement: 20 Rechter Teil: []
Sortiere [18]
nichts zu tun!
Sortiere []
nichts zu tun!
[0, 1, 2, 3, 8, 9, 13, 14, 16, 18, 20]
</code>