Materialien zum Unterricht

• Startseite
• Informatiksystem
  Grundlagen Analog und Digital Darstellung von Zahlen Binär rechnen Digitale Buchstaben Bilder in binär Digitale Farben
• Codierung
  Grundlagen Station 1 : Caesar-Verschlüsselung Station 2 : Codierungsscheiben Station 3 : Freimaurer-Code Station 4 : Geheimschrift von Polybius Station 5 : Raster-Codierung Station 6 : Stab-Codierung
• Daten & Informationen
  Definitionen Cookies 1 Cookies 2 Sicherheit & Schutz Fake?
• Netzwerke
• Algorithmen
  Eigenschaften Aufbau Darstellungen
• mBlock
  Einrichtung 1. Programm Quadrate n-Ecke Zahlenschloss
• Python
  KOAM-Modell Datentypen Operatoren Methoden Problemlöseprozess Grundlagen print() input() Selektion Zyklen break,pass,continue

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.

Weitere Sortierverfahren

Zurück