Materialien zum Unterricht

Sortieralgorithmen

Grundlagen

Sortieralgorithmen sind wichtig, da sie die Effizienz und Leistung vieler Anwendungen und Systeme verbessern. Sie ermöglichen eine schnellere Datenabfrage, optimieren Datenbankoperationen, organisieren Prozesse in Betriebssystemen und dienen als Grundlage für die Analyse anderer Algorithmen.

Grundbegriffe

Begriff Beschreibung Beispiel
Sortieren Prozess des Anordnens einer Menge von Elementen in einer bestimmten Reihenfolge. Karten sortieren nach aufsteigender Reihenfolge und Farbe.
Elemente Die zu sortierenden Datenobjekte. Zahlenkarten
Vergleichsoperator Ein Operator, der zwei Elemente vergleicht und angibt, ob sie in der gewünschten Reihenfolge stehen. Zahlenkarte_1 < Zahlkarte_2
Stabilität Ein Sortieralgorithmus ist stabil, wenn die relative Reihenfolge der Elemente mit gleichem Schlüssel erhalten bleibt. Wenn eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert wird, dann bleiben alle Personen mit gleichem Geburtsdatum alphabetisch sortiert.
In-place-Sortierung Ein Algorithmus, der keine zusätzlichen Speicherplatz benötigt und die Sortierung direkt in der Eingabesequenz durchführt. Karten in der Hand sortieren.

Anwendungsbereiche

Klassifizierung

Man unterscheidet Sortieralgorithmen in vergleichsbasierte und nicht-vergleichbasierte Sortieralgorihtm

Vergleichsbasierte Sortieralgorithmen vergleichen die Elemente paarweise miteinander und tauschen sie entsprechend der gewünschten Reihenfolge um.

Beispiele:
Bubble Sort, Insertion Sort, Selection Sort, Merge Sort und Quick Sort

Nicht-vergleichsbasierte Sortieralgorithmen sortieren die Elemente ohne direkte Paarvergleiche, sondern basierend auf anderen Eigenschaften der Elemente.

Beispiele:
Counting Sort, Radix Sort und Bucket Sort

Komplexität von Algorithmen

Die Effizienz der Sortieralgorithmen ist in den meisten Fällen vom Ausgangszustand der Datenmenge abhängig.

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.

Mehr zur Komplexität erfährst du unter:

Komplexität

Vergleichsbasierte Sortieralgorithmen

Auf der Webseite informatik.cc werden 5 Sortieralgorithmen vorgestellt.

Geh auf die Seite informatik.cc und teste die Verschiedenen Sortieralgorithmen aus.

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:

Programm-Name:"selectionsort.py" .

Setze den Selection Sort in Python um.

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 Funktion range() 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: Steckbriefe erstellen

Informiert euch in Gruppen von bis zu 3 Personen über eins der Sortierverfahren.
Notiert euch in einem Textdokument (Als STeckbrief):

Stellt das Sortierverfahren vor.

Sortierverfahren:

Material:

Aufgabe 3:

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

Sortierverfahren: