Daten sortieren


In vielen Situationen ist es notwendig, vorliegende Daten anhand bestimmter Kriterien zu sortieren. Bei Zahlen ist eine der einfachsten Sortierungen die Sortierung nach deren Größe. In diesem Kapitel lernen Sie einen Sortier-Algorithmus kennen, mit welchem man eine Menge von Zahlen der Größe nach sortieren kann.

Bevor eine Menge von Zahlen durch den Computer sortiert werden kann, muss diese gespeichert werden. Man könnte für jede Zahl eine eigene Variable anlegen, aber ein Programm würde dadurch sehr unübersichtlich werden. Sinnvoller ist es, die Menge von Zahlen in einer einzigen Variablen zu speichern.


Datenstruktur "Liste"

Auf die Elemente einer Liste kann über den Index der Liste zugegriffen werden.

Der Index einer Liste beginnt bei 0.

Für die im Beispiel angelegte Liste mit den Elementen 3, 9, 7, 1, 4 gilt also:

  • Element bei Index 0 ist 3
  • Element bei Index 1 ist 9
  • Element bei Index 2 ist 7
  • Element bei Index 3 ist 1
  • Element bei Index 4 ist 4

Beim Entwickeln eines Algorithmus mit Listen muss also genau beachtet werden, wie man den Zugriff auf Elemente einer Liste über den Index programmiert.


Inhalte einer Liste entnehmen

  • Menschen nummerieren eine Menge von Zahlen beginnend bei 1.
  • Informatiker*innen beginnen bei der Nummerierung von Listen bei 0.

Inhalte in einer Liste mit neuen Inhalten ersetzen


Zwei Zahlen sortieren

In einer Liste kann eine Menge von Zahlen gespeichert werden. Diese Menge von Zahlen kann mit Hilfe von Algorithmen bearbeitet werden. Beispielsweise kann die Liste von Zahlen nach der Größe sortiert werden.

Das folgende Beispiel funktioniert wie folgt:

  • Zuerst wird eine Liste mit zwei Zufallszahlen erzeugt.
  • Dann wird mit einer Falls-Abfrage geprüft, ob die Zahl beim Index 0 größer ist als die Zahl beim Index 1.
  • Wenn ja:
    • der Inhalt von Index 1 wird in eine Hilfsvariable namens "temp" gespeichert,
    • in Index 0 wird der Inhalt von Index 1 gespeichert,
    • in Index 1 wird der Inhalt von "temp" gespeichert.
  • Wenn nein:
    • dann wird nichts gemacht


Fünf Zahlen sortieren

Das folgende Beispiel funktioniert wie folgt:

  • Zuerst wird eine Liste mit fünf Zufallszahlen erzeugt.
  • Mit Hilfe von zwei Wiederholungsschleifen werden die Zahlen solange durchlaufen, bis sie der Größe nach sortiert sind.
  • Dazu wird mit einer Falls-Abfrage geprüft, ob die Zahl beim Index 0 größer ist als die Zahl beim Index 1.
  • Wenn ja:
    • der Inhalt von Index 1 wird in eine Hilfsvariable namens "temp" gespeichert,
    • in Index 0 wird der Inhalt von Index 1 gespeichert,
    • in Index 1 wird der Inhalt von "temp" gespeichert.
  • Wenn nein:
    • dann wird nichts gemacht


Sortierreihenfolge umkehren

  • Ändern Sie den Bubble-Sort-Algorithmus so, dass die Zahlen nicht von kleinster Zahl zu größter Zahl, sondern umgekehrt von größter Zahl zu kleinster Zahl sortiert werden.

Optimierung des Algorithmus

Der erste Sortieralgorithmus benötigt bei \(n\) Zahlen \(n^2\) Schleifen-Wiederholungen. Das kann bei großen Zahlenmengen, die sortiert werden sollen, schnell sehr viel werden.

Der Algorithmus soll so umgebaut werden, dass erkannt wird, wann die Zahlen sortiert sind und der Algorithmus früher gestoppt wird.