4.5 Punktwolken sortieren
Das aufsteigende und absteigende Sortieren von Zahlen wird auf der Seite 3.3.2.1,
Seite 3.3.2.2 und Seite 3.3.2.3 bereits behandelt.
Unspektakulär sind dabei die Ausführungen der am Computer implementierten Sortierprogramme.
- Nach den Eingaben unsortierter Zahlen in die Listen führen die Programme das Sortieren aus.
- Danach geben die Programme die sortierten Zahlen in den Listen aus.
Unspektakulär deshalb, weil unmittelbar nach den Programmausführungen sofort die Listen mit den sortierten Zahlen ausgegeben werden – wie dies beispielsweise in der Abbildung 1 zu sehen ist.
Obwohl anhand der Quelltexte durchaus ersichtlich ist, dass die Programme auf unterschiedliche Weise sortieren, ist es schwer, sich die Abläufe des Sortierens vorzustellen.
Um sich also vorzustellen, wie unterschiedlich die Programme das Sortieren ausführen, kann das grafische Sortieren von Punktwolken behilflich sein (Abbildung 2).
Programm »punktwolke1.py«
Im Programm »punktwolke.py« werden die Punkte der Wolke nach ihren y-Koordinaten
import tkinter as tk
import random
# grafische Oberfläche
root = tk.Tk()
root.title("Punktwolke sortieren")
root.resizable(False, False)
canvas=tk.Canvas (root, width=400, height=400,\
background="black")
canvas.pack(fill=tk.BOTH, expand=True)
y=[]
punkt=[]
# Punktwolke erzeugen
for i in range(0, 41):
zahl=random.randint(0, 400)
y.append(zahl)
punkt.append(canvas.create_rectangle(i*10,y[i],\
i*10, y[i], outline="yellow"))
punkt[i]
# Punktwolke sortieren
for i in range(0, 40):
for j in range(i+1, 41):
if y[i]>y[j]:
canvas.delete(punkt[i])
canvas.delete(punkt[j])
# Tauschen
help=y[i]
y[i]=y[j]
y[j]=help
punkt[i]=canvas.create_rectangle(i*10,y[i],\
i*10, y[i], outline="yellow")
punkt[j]=canvas.create_rectangle(j*10,y[j],\
j*10, y[j], outline="yellow")
root.update()
root.mainloop()
| 13. Zeile | Der Variable »y« wird die leere Liste als Wert zugewiesen. |
| 14. Zeile | Der Variable »punkt« wird die leere Liste als Wert zugewiesen. |
| 17. bis 22. Zeile | Enthält die »for-Schleife« zum Erzeugen der Punktwolke, die aus 41 Punkten besteht (0 bis 40 sind 41 Punkte). |
| 18. Zeile | Die Variable »zahl« bekommt per Zufall eine Ganzzahl zwischen 0 und 400 (einschließlich) zugewiesen. |
| 19. Zeile | Der Wert der Variable »zahl« wird in die Liste »y« eingefügt. |
| 20. und 21. Zeile | Der Punkt mit den Koordinaten P(i⋅10,y[i]) wird in die Liste »punkt« eingefügt. |
| 22. Zeile | Der i-te Punkt wir im Canvas-Widget dargestellt. |
| 25. bis 38. Zeile |
Enthält die äußere und innere »for-Schleife« zum sortieren der Punkte der Punktwolke (vgl. u. a. Seite 3.3.2.1). |
| 28. und 29. Zeile | Der i-te und der j-te Punkt werden im Canvas-Widget gelöscht. |
| 34. bis 37. Zeile | Der i-te und der j-te Punkt werden nach dem Tausch der Koordinaten im Canvas-Widget dargestellt. |
| 38. Zeile | Die veränderten Darstellungen im Canvas-Widget erfolgen sofort an dieser Stelle. |
Allerdings ist die das grafische Darstellen des Sortierens im Canvas-Widget mit einem bereits genannten Problem
verbunden. Im Koordinatensystem des Canvas-Widget ist die y-Achse nach
Die Tatsache, dass die y-Achse des Koordinatensystem des Canvas-Widget nach
Einzig zu beachten ist, dass das aufteigende Sortieren absteigend und das absteigende Sortieren aufsteigend im Canvas-Widget dargestellt wird
Aufgabe A77
Übertrage den Quelltext als Programm auf den Computer.
Führe das Programm aus und teste, ob es fehlerfrei läuft und den gestellten Anforderungen entspricht.
Aufgabe A78
Implementiere ein Programm »punktwolke2.py« am Computer.
Das Programm sortiert grafisch eine Punktwolke mit Hilfe des Sortierverfahrens »Bubble Sort« aufsteigend.
Führe das Programm aus und teste, ob es fehlerfrei läuft und den gestellten Anforderungen entspricht.
Aufgabe A79
Implementiere ein Programm »punktwolke3.py« am Computer.
Das Programm sortiert grafisch eine Punktwolke mit Hilfe des Sortierverfahrens »Insertion Sort« aufsteigend.
Führe das Programm aus und teste, ob es fehlerfrei läuft und den gestellten Anforderungen entspricht.
Ein Vergleich der Ausführungen der drei Programme ist für das Verstehen der Sortierverfahren ganz bestimmt nutzbringend.