next up previous contents
Nächste Seite: 2.1 Hilfsklassen Aufwärts: hamster4 Vorherige Seite: 1.3 Aufbau dieses Buches   Inhalt


2. Sortieren

Die sicher am intensivsten in der Informatik untersuchten Algorithmen sind Sortieralgorithmen. Sie sind insbesondere deshalb interessant, weil Sortieren zu den häufigsten Teilaufgaben beim Lösen bestimmter Probleme gehört.

Als Sortieren bezeichnet man dabei das Ordnen einer Menge von Datensätzen, d.h. diese sollen in eine bestimmte Reihenfolge gebracht werden. Die Datensätze können eine einfache Struktur aufweisen, wie Zahlen. Sie können jedoch auch komplex sein, bspw. Personen mit Name, Alter und Adresse.

Das Kriterium, nach dem geordnet werden soll, bezeichnet man als Schlüssel. Personen könnten bspw. nach ihrem Namen oder nach ihrem Alter sortiert werden. Entsprechend ist der Name oder das Alter der Sortierschlüssel.

Eine Voraussetzung beim Sortieren ist, dass eine eine (totale) Ordnung auf den Schlüsseln existiert, d.h. dass für zwei beliebige Schlüssel a und b gilt, das a kleiner als b oder b kleiner als a ist. Bestehen die Schlüssel aus Zahlen oder Zeichenketten wird im Allgemeinen nach der bekannten numerischen bzw. lexikographischen Ordnung sortiert.

In diesem Abschnitt werden die sechs bekanntesten Sortieralgorithmen vorgestellt:

Zu jedem Algorithmus werden zunächst die generelle Idee skizziert und der allgemein gültige Sourcecode eingeführt und erläutert. Sortiert werden dabei Arrays mit int-Werten, und zwar gemäß der numerischen Ordnung in aufsteigender Reihenfolge. Für jeden Algorithmus wird das folgende Interface implementiert (SortierAlgorithmus.ham):

public interface SortierAlgorithmus {
  // sortiert das uebergebene Array in aufsteigender Reihenfolge
  public void sortiere(int[] zahlen);
}

Anschließend wird jeweils ein Hamster-Programm vorgestellt, das den entsprechenden Sortieralgorithmus visualisiert, d.h. die Hamster zeigen Ihnen, wie der Algorithmus prinzipiell funktioniert. Sortiert werden dabei Körnerhaufen, und zwar von Hamstern spezieller Klassen, die das folgende Interface implementieren (SortierHamster.ham):

public interface SortierHamster {
  // Der Standard-Hamster steht mit Blickrichtung OST irgendwo im 
  // Territorium.  Ein Vertretungshamster soll die Koernerhaufen 
  // bis zur nächsten Wand in aufsteigender Reihenfolge sortieren.
  public void sortiereKoernerHaufen();
}

Die Hamster-Programme sind nicht primär zum Lesen, sondern zum Ausführen gedacht. Machen Sie daher folgendes:

Nach der Vorstellung jedes Sortieralgorithmus folgt noch eine kurze Analyse der Eigenschaften des Algorithmus. Insbesondere wird analysiert, wie schnell der Algorithmus ist.2.1

Weiterhin wird die Eigenschaft der Stabilität betrachtet. Ein Sortieralgorithmus heisst stabil, wenn die relative Reihenfolge gleicher Schlüssel beibehalten wird. Diese Eigenschaft ist von Interesse, wenn die Datensätze nicht nur aus Schlüsseln bestehen. Nehmen wir bspw. wieder zu sortierende Personen mit Name und Alter. Angenommen, die Personen seien bereits alphabetisch nach ihren Namen sortiert. Werden sie nun nach ihrem Alter sortiert, so sind nachher bei stabilen Verfahren Personen mit dem gleichen Alter auch weiterhin alphabetisch geordnet.

Weiterhin interessant ist die Frage, ob ein bestimmter Sortieralgorithmus in-place arbeitet. Man sagt, ein Algorithmus arbeitet in-place, wenn er außer dem für die Speicherung der zu sortierenden Daten benötigten Speicher nur eine konstante - d.h. von der Größe der zu sortierenden Datenmenge unabhängige - Menge von Speicher benötigt.

Zum Schluss des Kapitels folgt eine kurze Zusammenfassung sowie ein paar Anmerkungen zu weiteren Aspekten der Sortierung. Insbesondere wird gezeigt, wie die Programme verändert werden müssen, wenn anstelle von Arrays mit int-Werten, Arrays mit Zeichenketten bzw. beliebigen Objekten sortiert werden sollen.



Unterabschnitte
next up previous contents
Nächste Seite: 2.1 Hilfsklassen Aufwärts: hamster4 Vorherige Seite: 1.3 Aufbau dieses Buches   Inhalt
Dietrich Boles 2005-04-18