30. Sortieren¶
Die binäre Suche funktioniert nur bei Listen, die in der richtigen Reihenfolge sind. Wie können Programme eine Liste in der richtigen Reihenfolge erstellen? Wie sortiert ein Programm eine Liste von Elementen, wenn der Benutzer auf eine Spaltenüberschrift klickt oder auf andere Weise etwas Sortiertes benötigt?
Dafür gibt es mehrere Algorithmen. Die zwei einfachsten Algorithmen zum Sortieren sind Selectionsort und Insertionsort. Es gibt auch andere Sortieralgorithmen wie Shellsort, Mergesort, Heapsort und Quicksort.
Der beste Weg, um eine Vorstellung davon zu bekommen, wie diese Sortieralgorithmen funktionieren, ist, sie zu beobachten. Um die gängigen Sortieralgorithmen in Aktion zu sehen, besuche diese hervorragende Website:
http://www.sorting-algorithms.com
Jeder Sortieralgorithmus hat Vor- und Nachteile. Einige sortieren eine Liste schnell, wenn die Liste fast in richtigen Reihenfolge ist. Einige sortieren eine Liste schnell, wenn die Liste in einer völlig zufälligen Reihenfolge vorliegt. Andere Listen werden schnell sortiert, benötigen jedoch mehr Speicher. Es ist wichtig zu verstehen, wie Sortieralgorithmen funktionieren, um den richtigen Algorithmus für ein Programm auszuwählen.
30.1. Werte vertauschen¶
Bevor wir sortieren lernen, müssen wir lernen, wie Werte von zwei Variablen gegeneinander ausgetauscht werden. Dies ist eine übliche Operation in vielen Sortieralgorithmen. Angenommen, ein Programm hat eine Liste, die wie folgt aussieht:
my_list = [15, 57, 14, 33, 72, 79, 26, 56, 42, 40]
Der Entwickler möchte die Elemente an den Positionen 0 und 2 tauschen, die die Zahlen 15 beziehungsweise 14 enthalten. Siehe Abbildung 18.1.
Abbildung 18.1: Werte in einem Array austauschen¶
Ein erster Versuch, diesen Code zu schreiben, könnte ungefähr so aussehen:
my_list[0] = my_list[2]
my_list[2] = my_list[0]
Abbildung 18.2: Falscher Versuch, Array-Werte auszutauschen¶
In Abbildung 18.2 erhalten wir eine Vorstellung davon, was passieren würde. Dies funktioniert eindeutig nicht. Die erste Zuweisung list[0] = list[2] bewirkt, dass der in Position 0 vorhandene Wert 15 mit dem Wert 14 in Position 2 überschrieben wird und unwiederbringlich verloren geht. Die nächste Zeile mit list[2] = list[0] kopiert die 14 einfach zurück in Zelle 2, die bereits eine 14 enthält.
Um dieses Problem zu beheben, sollte man die Werte in einem Array in drei Schritten austauschen. Es ist erforderlich, eine temporäre Variable zu erstellen, um einen Wert während der Austauschoperation zu speichern. Siehe Abbildung 18.3. Der Code für den Austausch sieht folgendermaßen aus:
temp = my_list[0]
my_list[0] = my_list[2]
my_list[2] = temp
Die erste Zeile kopiert den Wert von Position 0 in die Variable temp. Dadurch kann der Code die Position 0 mit dem Wert in Position 2 überschreiben, ohne dass Daten verloren gehen. Die letzte Zeile nimmt den alten Wert von Position 0, der derzeit in der Variablen temp enthalten ist, und platziert ihn an Position 2.
Abbildung 18.3: Richtige Methode zum Austauschen von Array-Werten¶
30.2. Selectionsort¶
Der Algorithmus beginnt mit dem Betrachten des Elements 0. Anschließend durchsucht der Code noch den Rest der Liste von Element 1 bis n-1, um die kleinste Zahl zu finden in der Liste zu finden. Die kleinste Zahl wird mit dem Element 0 getauscht. Jetzt steht die kleinste Zahl an der Position 0. Der Rest der Liste ist noch unsortiert. Der Algorithmus sucht dann das kleinste Element in der Restliste und beginnt die Suche mit dem Element 1, dann zu 2 und so weiter. Graphisch sieht die Sortierung wie in Abbildung 18.4 aus.
Abbildung 18.4: Selectionsort¶
Der Code für Selectionsort besteht aus zwei verschachtelten Schleifen. Die äußere Schleife verfolgt die aktuelle Position, in die der kleinste Wert kommen soll. Die innere Schleife beginnt an der aktuellen Position und sucht nach dem kleinsten Wert nach rechts. Wenn die innere Schleife den kleinsten Wert gefunden hat, vertauscht der Algorithmus den Wert an der aktuellen Position mit dem Wert an der Position mit dem kleinsten Wert.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def selection_sort(my_list):
""" Sort a list using the selection sort """
# Loop through the entire array
for cur_pos in range(len(my_list)):
# Find the position that has the smallest number
# Start with the current position
min_pos = cur_pos
# Scan left to right (end of the list)
for scan_pos in range(cur_pos + 1, len(my_list)):
# Is this position smallest?
if my_list[scan_pos] < my_list[min_pos]:
# It is, mark this position as the smallest
min_pos = scan_pos
# Swap the two values
temp = my_list[min_pos]
my_list[min_pos] = my_list[cur_pos]
my_list[cur_pos] = temp
|
Die äußere Schleife läuft immer \(n\) mal. Die innere Schleife wird durchschnittlich \(\frac{n}{2}\) mal pro Lauf der äußeren Schleife ausgeführt. Daher wird die innere Schleife insgesamt \(n\cdot\frac{n}{2}\) oder \(\frac{n^2}{2}\) mal ausgeführt.
Dies ist unabhängig davon der Fall, ob die Liste schon der Größe nach sortiert ist oder nicht. Die Effizienz der Schleifen kann verbessert werden, indem geprüft wird, ob min_pos und cur_pos vor Zeile 20 gleich sind. Wenn diese Variablen gleich sind, müssen die drei Zeilen des Austausch-Codes nicht ausgeführt werden.
Um den obigen Code des Selectionsort zu testen, kann das folgende Programm verwendet werden. Die erste Funktion gibt die Liste aus. Der nächste Programmcode erstellt eine Liste von Zufallszahlen, gibt sie aus, sortiert sie und gibt sie dann erneut aus. In Zeile 5 richtet die print-Anweisung die Zahlen mit der rechtsbündig aus, damit die Zahlenspalte besser lesbar ist. Die Formatierung von print-Ausgaben wird in einem späteren Kapitel behandelt.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # Before this code, paste the selection sort and import random
def print_list(my_list):
for item in my_list:
print("{:3}".format(item), end="")
print()
# Create a list of random numbers
my_list = []
for i in range(10):
my_list.append(random.randrange(100))
# Try out the sort
print_list(my_list)
selection_sort(my_list)
print_list(my_list)
|
Eine Animation des Selectionsort findest du unter:
http://www.sorting-algorithms.com/selection-sort
Durchsuche YouTube nach „selection sort dance“ oder verwende diesen Link, um eine wirklich einzigartige Visualisierung von Selectionsort zu erhalten:
Du kannst den Code auch mit Selection Sort on Python Tutor nachverfolgen.
30.3. Insertionsort¶
Insertionsort ähnelt Selectionsort in der Funktionsweise der äußeren Schleife. Insertionsort beginnt auf der linken Seite des Arrays und arbeitet sich nach rechts vor. Der Unterschied besteht darin, dass Insertionsort nicht das kleinste Element auswählt und an die richtige Stelle setzt. Insertionsort wählt das nächste Element rechts von dem aus, was in der Liste bereits sortiert wurde und vergleicht diesen Wert mit jeden Wert links davon in dem bereits sortierten Listenteil. Der Algorithmus schiebt jedes größere Element in dem bereits sortierten Listenteil nach rechts, bis es an die richtige Stelle zum Einfügen gelangt. Graphisch sieht es aus wie in Abbildung 18.5.
Abbildung 18.5: Insertionsort¶
Insertionsort unterteilt die Liste in zwei Abschnitte, den sortierten Teil und den unsortierten Teil. In jeder Runde der äußeren Schleife greift der Algorithmus das nächste unsortierte Element und fügt es in die den sortierten Teil der Liste ein.
Im folgenden Code markiert key_pos die Grenze zwischen den sortierten und unsortierten Teilen der Liste. Der Algorithmus scannt links von key_pos mit der Variablen scan_pos. Beachte, dass scan_pos beim Insertionsort nach links und nicht nach rechts läuft. Jede Zellenposition, die größer als key_value ist, wird um eine Position nach oben (nach rechts) verschoben.
Wenn die Schleife eine Position findet, die kleiner als key_value ist, stoppt sie und setzt key_value rechts davon ein.
Die äußere Schleife vom Insertionsort wird \(n\) mal ausgeführt. Für jeden Durchgang der äußeren Schleife wird die innere Schleife durchschnittlich \(\frac{n}{4}\) mal ausgeführt, wenn die Liste zufällig gemischt ist. Insgesamt würde die innere Schleife \(n\cdot\frac{n}{4}\) mal oder vereinfacht \(\frac{n^2}{4}\) mal laufen.
Was wirklich wichtig ist: Befindet sich die Liste bereits in der Nähe einer sortierten Liste, wird die innere Schleife nicht sehr häufig ausgeführt, und die Sortierzeit liegt näher bei n. Insertionsort ist der schnellste Algorithmus für nahezu sortierte Listen. Wenn die Liste umgekehrt sortiert ist, ist Insertionsort fürchterlich.
Selectionsort ist es eigentlich egal, in welcher Reihenfolge sich die Liste am Anfang befindet. Er verhält sich trotzdem gleich.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | def insertion_sort(my_list):
""" Sort a list using the insertion sort """
# Start at the second element (pos 1).
# Use this element to insert into the
# list.
for key_pos in range(1, len(my_list)):
# Get the value of the element to insert
key_value = my_list[key_pos]
# Scan from right to the left (start of list)
scan_pos = key_pos - 1
# Loop each element, moving them up until
# we reach the position the
while (scan_pos >= 0) and (my_list[scan_pos] > key_value):
my_list[scan_pos + 1] = my_list[scan_pos]
scan_pos = scan_pos - 1
# Everything's been moved out of the way, insert
# the key into the correct location
my_list[scan_pos + 1] = key_value
|
Eine Animation der Insertionsort findet man unter:
http://www.sorting-algorithms.com/insertion-sort
Durchsuche YouTube nach „insertion sort dance“ oder verwende diesen Link, um eine andere Tanzinterpretation zu erhalten:
Du kannst den Code mit Insertion Sort on Python Tutor nachverfolgen.
30.4. Vollständiges Sortierbeispiel¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | import random
def selection_sort(my_list):
""" Sort a list using the selection sort """
# Loop through the entire array
for cur_pos in range(len(my_list)):
# Find the position that has the smallest number
# Start with the current position
min_pos = cur_pos
# Scan left to right (end of the list)
for scan_pos in range(cur_pos + 1, len(my_list)):
# Is this position smallest?
if my_list[scan_pos] < my_list[min_pos]:
# It is, mark this position as the smallest
min_pos = scan_pos
# Swap the two values
temp = my_list[min_pos]
my_list[min_pos] = my_list[cur_pos]
my_list[cur_pos] = temp
def insertion_sort(my_list):
""" Sort a list using the insertion sort """
# Start at the second element (pos 1).
# Use this element to insert into the
# list.
for key_pos in range(1, len(my_list)):
# Get the value of the element to insert
key_value = my_list[key_pos]
# Scan from right to the left (start of list)
scan_pos = key_pos - 1
# Loop each element, moving them up until
# we reach the position the
while (scan_pos >= 0) and (my_list[scan_pos] > key_value):
my_list[scan_pos + 1] = my_list[scan_pos]
scan_pos = scan_pos - 1
# Everything's been moved out of the way, insert
# the key into the correct location
my_list[scan_pos + 1] = key_value
# This will point out a list
# For more information on the print formatting {:3}
# see the chapter on print formatting.
def print_list(my_list):
for item in my_list:
print(f"{item:3}", end="")
print()
def main():
# Create two lists of the same random numbers
list_for_selection_sort = []
list_for_insertion_sort = []
list_size = 10
for i in range(list_size):
new_number = random.randrange(100)
list_for_selection_sort.append(new_number)
list_for_insertion_sort.append(new_number)
# Print the original list
print("Original List")
print_list(list_for_selection_sort)
# Use the selection sort and print the result
print("Selection Sort")
selection_sort(list_for_selection_sort)
print_list(list_for_selection_sort)
# Use the insertion sort and print the result
print("Insertion Sort")
insertion_sort(list_for_insertion_sort)
print_list(list_for_insertion_sort)
main()
|