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.
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
Testen von der Python-Shell aus:
>>> 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]
…wenn das nicht genial ist… Lässt man die Zwischenausgaben weg, dann ist es ein 7-Zeiler!
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)
Ein Probelauf von der Shell aus:
>>> 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]