3.3.2.3 Sortierverfahren Insertion Sort
Auf dieser Seite vermittelt das Programm »insertionsort.py« einen Eindruck, wie die Python-Methoden »sort« und »sorted« Ganzzahlen innerhalb einer Liste aufsteigend sortieren.
Programm » insertionsort.py«
In der Abbildung 1 ist der Algorithmus des Sortierverfahrens Insertion Sort dargestellt, der dem Programm zugrunde liegen soll.
In der Abbildung 2 ist die Ausführung des Insertion-Sort-Algorithmus in einer Tabelle dokumentiert. Aus der Tabelle geht hervor, wie der Algorithmus die Ganzzahlen in der Liste aufsteigend sortiert.
Aufgabe A33
Dokumentiere in einer Tabelle – wie in der Abbildung 2 dargestellt – die Ausführung des Algorithmus Insertion Sort:
- Verwende statt der Liste [5, -2, 13, 0, 9] die Liste [56, 7, -21, 0, -6, 1]
Versuche zu vertstehen, wie der Algoritmus die Ganzzahlen in der Liste aufsteigend sortiert.
Aufgabe A34
Implementiere ein Programm »insertionsort.py« am Computer.
Das Programm soll aus drei Teilen bestehen:
- der Callback-Funktion »eingeben«
- der Callback-Funktion »sortieren«
- der grafischen Benutzeroberfläche GUI - dem Hauptfenster (wie z. B. in der Abbildung 3 dargestell)
Das Programm soll das Folgende leisten:
- (E) Eingabe einer Liste, deren Elemente Ganzzahlen sind
- (V) die Elemente der Liste aufsteigend sortieren.
- (A) die aufsteigend sortierte Liste ausgeben
Führe das Programm u. a. mit folgenden Eingaben aus und teste, ob es fehlerfrei läuft und den gestellten Anforderungen entspricht:
- [5, -2, 13, 0, 9]
- [67, 12, -4, 45, 0, 2, 98, -34, 45]
- [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Weitere (effizientere) Sortierverfahren sind:
- Quicksort
- Mergesort
- Heapsort
- [1]
Der Bereich von »range(1, anzahl)« umfasst die Zahlen von 1 bis ausschließlich anzahl:
-
hat »anzahl« beispielsweise den Wert 5, umfasst der Bereich »range(1, anzahl)«
die Zahlen
1, 2, 3 und 4.
-
hat »anzahl« beispielsweise den Wert 5, umfasst der Bereich »range(1, anzahl)«
die Zahlen