3.3.2.1 Sortierverfahren Selection Sort

Auf dieser Seite vermittelt das Programm »selectionsort.py« einen Eindruck davon, wie die Python-Methoden »sort« und »sorted« Ganzzahlen innerhalb einer Liste aufsteigend sortieren.

Programm »selectionsort.py«

Im Programm »selectionsort.py« dient die Callback-Funktion »sortieren« dem aufsteigenden Sortieren der Elemente (Ganzzahlen) der Liste »liste«.

In der Abbildung 1 ist der Algorithmus des Sortierverfahrens Insertion Sort dargestellt, der dem Programm zugrunde liegt.

Bild 58
Abbildung 1: Darstellung des Selection-Sort-Algorithmus

In der Abbildung 2 ist die Ausführung des Algorithmus in einer Tabelle dokumentiert:

  • aus der Tabelle geht hervor, wie der Algorithmus die Ganzzahlen in der Liste aufsteigend sortiert
Bild 59
Abbildung 2: Ausführung des Selectionsort-Algorithmus
Übung

Aufgabe A29

Dokumentiere in einer Tabelle – wie in der Abbildung 2 dargestellt – die Ausführung des Algorithmus Selection Sort:

  • verwende dazu die Liste [56, 7, -21, 0, -6, 1]

Versuche zu vertstehen, wie der Algoritmus die Ganzzahlen in der Liste aufsteigend sortiert.

Der in der Abbildung 1 dargestellt Selection-Sort-Algorithmus ist In der Callback-Funktion »sortieren« implementiert.

Quelltext der Callback-Funktion »sortieren« 
liste=[]

# Callback-Funktion
def sortieren():
    global liste
    anzahl=len(liste)
    for i in range(anzahl-1):
        for j in range(i+1, anzahl):
            if liste[i]>liste[j]:
                hilf=liste[i]
                liste[i]=liste[j]
                liste[j]=hilf
    label3.config(text=f"Sortierte Liste: {liste}")
    entry.configure(state=tk.DISABLED)
    button1.configure(state=tk.DISABLED)
    button2.configure(state=tk.DISABLED)
Erklärungen zum Quelltext
1. Zeile Der globale Variable »liste« wird die leere Liste [] als Wert zugewiesen.
4. bis 16. Zeile Die Callback-Funktion »sortieren« wird deklariert.
5. Zeile Die globale Variable »liste« wird in die Callback-Funktion »sortieren« eingebunden.
6. Zeile Die Variable »anzahl« bekommt die Anzahl der Elemete der Liste zugewiesen.
7. bis 12. Zeile Enthält die äußere »for-Schleife« des Sortieralgorithmus.[1]
8. bis 12. Zeile Enthält die innere »for-Schleife« des Sortieralgorithmus.[2]
9. bis 12. Zeile Enthält die »if-Anweisung« mit einem Bedingungszweig.
10. bis 12. Zeile Der Tausch der Werte der Variablen »liste[i]« und »liste[j]« findet mit Hilfe der Variable »hilf« statt.
13. Zeile Der Wert der Variable »liste« wird in einem f-String als Zeichenkette ausgegeben.
14. bis 16. Zeile Die beiden Button »Ganzzahl in die Liste einfügen« und »Liste aufsteigend sortieren« werden deaktiviert.
Übung

Aufgabe A30

Implementiere ein Programm »selectionsort.py« am Computer.

Das Programm »selectionsort.py« soll aus drei Teilen bestehen:

  • der Callback-Funktion »eingeben«
  • der Callback-Funktion »sortieren«
  • der grafischen Benutzeroberfläche GUI - dem Hauptfenster (wie beispielsweise in der Abbildung 3 dargestell)
Bild 60
Abbildung 3: Ein Vorschlag für das Hauptfenster

Das Programm »selectionsort.py« soll das Folgende leisten:

  • (E) Eingabe einer Liste, deren Elemente Ganzzahlen sind
  • (V) die Elemente (Ganzzahlen) 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]

Auf der Seite 4.5 wird das Sortierverfahren Selection Sort nochmals unter grafischen Aspekt aufgegriffen.

  1. [1] Der Bereich »range(ianzahl)-1« umfasst die Zahlen von 0 bis ausschließlich »anzahl-1«:
    • hat beispielsweis »anzahl-1« den Wert 6, umfasst der Bereich »range(anzahl-1)« die Zahlen 0, 1, 2, 3, 4 und 5.
  2. [2] Der Bereich »range(i+1, anzahl)« umfasst die Zahlen von »i+1« bis ausschließlich »anzahl«:
    • hat beispielsweis »i« den Wert 3 und »anzahl« den Wert 7, umfasst der Bereich »range(i+1, anzahl)« die Zahlen 4, 5 und 6.