Materialien zum Unterricht



Sortieralgorithmen


Stabilität von Sortierverfahren

Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.
Wenn z.B. eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert wird, dann bleiben unter einem stabilen Sortierverfahren alle Personen mit gleichem Geburtsdatum alphabetisch sortiert.


Komplexität von Sortierverfahren

Die verschiedenen Algorithmen können unterschiedlich effizient beim Sortieren der Datenmengen sein.
Welches Sortierverfahren im Endeffekt als "bester Sortieralgorithmus" bezeichnet werden kann, muss immer individuell und situativ entschieden werden.

Zwei Entscheidungsfaktoren bezüglich der Komplexität sind dabei die Laufzeit und der benötigte Speicherplatz des Algorithmus.


Laufzeit

Die Effizienz der Sortieralgorithmen ist in den meisten Fällen vom Ausgangszustand - der Anordnung der Datenmenge zur Zeit der Eingabe - abhängig.
Dabei wird immer zwischen Best Case, Average Case und Worst Case unterschieden.

Beispiel:
Die Liste ist von Beginn an korrekt sortiert.
Hier brauchen die meisten Sortieralgorithmen weniger Zeit zum Sortieren.
Das wäre dann der beste Fall, da der Algorithmus dadurch noch effizienter ist.


Selection Sort

Beim Selection Sort Unterteilt man seine Liste in 2 Bereiche: sortiert (links) und unsortiert (rechts).
Der sortierte Bereich ist zu Beginn leer.

Ablauf:

  1. Man sucht im rechten, unsortierten Teil der Liste nach dem kleinsten Element.
    Dazu merkt man sich das erste Element der unsortierten Liste und vergleicht dieses mit den folgenden Elementen
    Sollte ein kleineres Element gefunden werden, wird dieses gemerkt und damit weiter verglichen.
  2. Das kleinste Element der unsortierten Liste wird nun an die 1. Stelle der unsortierten Liste gesetzt.
  3. Die Grenze zwischen dem sortierten und dem unsortiertem Array wird um 1 nach rechts verschoben.
    Dadurch wächst die sortierte Liste, während die unsortierte Liste kürzer wird.

Aufgabe 1:

Setze den Selection Sort in Python um.

Nenne das Programm "selectionsort.py" .

Tipp 1: PAP
Überlege dir einen Programmablaufplan.
Wie wird das Array durchlaufen?
Wie wird der Vergeleich realisiert?
Wie wird der Tausch der Positionen in der Liste realisiert?
Tipp 2: Listenteilung
Es soll auf der Liste gearbeitet werden.
Die Liste wird dafür zweigeteilt.
Wie lässt man nur die unsortierte Liste durchlaufen?
Tipp 3: Ergänzung Tipp 2
Man kann Tipp 2 mitder Funktionrange()realisieren.

Tipp 4: Wertetausch
Man vertauscht die Werte über den Index.
sequentielle Datentypen
Tipp 5: Wertetausch 2
Programmablaufplan

Tipp 6: Komplett Lost
Programmablaufplan

Lösung Version 1
Link zur Lösung 1
Lösung Version 2
Link zur Lösung 2

Weitere Sortierverfahren

Aufgabe 2:

Informiert euch in Gruppen von bis zu 3 Personen über eine der 3 Sortierverfahren. Notiert euch in einem Textdokument:

Stellt das Sortierverfahren vor.

Sortierverfahren:

Aufgabe 3:

Wähle einen der drei vorgestellten Algorithmen aus und setze ihn in Python um.

Sortierverfahren:




Zurück