In der 3. Auflage des Lehrbuchs Grundkurs Algorithmen und Datenstrukturen wurden diese Algorithmen ohne Generizität veröffentlicht. Hier sind ihre generischen Versionen aus der 4. Auflage.
Die Textfärbung stammt aus Eclipse. Die Kommentare in grün erläutern den Algorithmus, die Kommentare in rot erläutern die verwendete Generizität.
Die folgenden Sortierverfahren (außer Quick Sort) haben eine konstante Speicherkomplexität, d.h. die Größe des benötigten Speichers ist unabhängig von der zu sortierenden Datenmenge (in einer Reihung).
Benachbarte Elemente einer Reihung werden (wenn nötig) ausgetauscht, und zwar oft genug, damit zum Schluss die Reihung garantiert sortiert vorliegt. Dieser einfachster Sortieralgorithmus ist jedoch nur für kleine Datenmengen geeignet, zumal seine Zeitkomplexität ist n2.
Visualisierung in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static <Element extends Comparable<Element>> void bubbleSort(Element[] sammlung) {
/* Der Typparameter Element ist der Typ der zu sortierenden Objekte;
(er wird vom Compiler beim Aufruf aus dem Methodenparameter ermittelt).
Diese Objekte müssen untereinander vergleichbar sein, d.h. ihre Klasse muss die Methode compareTo enthalten.
Dies wird sichergestellt, indem Element extends Comparable.
Comparable ist jedoch selbst eine generische Schnittstelle.
Ihr Typparameter wird als Parametertyp von compareTo benötigt.
Daher stellt die geschachtelte Generizität sicher, dass compareTo zwei Objekte vom selben Typ miteinander vergleicht. */
for (int i = 0; i < sammlung.length; i++) for (int j = 0; j < sammlung.length-1; j++) if (sammlung[j+1].compareTo(sammlung[j]) < 0) { // vergleichen // hier wird die Vergleichsmethode aus dem generischen Typparameter Comparable aufgerufen final Element temp = sammlung[j+1]; // austauschen sammlung[j+1] = sammlung[j]; sammlung[j] = temp; } }
Character[] reihung = new Character[11]; ... // 11 Character-Objekte erzeugen bubbleSort(reihung); // aktueller Typparameter ist (implizit) Character, welche implements Comparable<Character>
class Kunde implements Comparable<Kunde> { ... } // hier muss die Funktion compareTo(Kunde) implementiert werden, die zwei Kunde-Objekte miteinander (z.B. nach Kundennummer) vergleicht Kunde[] kundenkartei = new Kunde[karteigröße]; ... // Kunde-Objekte erzeugen bubbleSort(kundenkartei); // aktueller Typparameter ist (implizit) Kunde
In der verbesserte Version des Bubble Sort findet der Durchlauf abwechselnd von oben und von unten statt. Außerdem werden die Durchläufe vorzeitig abgebrochen, wenn die Reihung schon sortiert ist. Der Algorithmus ist in den meisten Fällen schneller, aber die Zeitkomplexität ist immer noch n2, d.h. der durchschnittlicher Zeitverbrauch wächst mit der Datenmenge quadratisch: Ein doppelt (dreimal, zehnmal) so große Reihung zu sortieren dauert im Durchschnitt viermal (neunmal, hundertmal) so lang.
Visualisierung in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static <E extends Comparable<E>> void shakerSort(E[] sammlung) { boolean austausch; int links = 1; // anfangen beim zweiten Element int rechts = sammlung.length-1; int fertig = rechts;
do {
austausch = false;
for (int ab = rechts; ab >= links; ab--) // abwärts
if (sammlung[ab].compareTo(sammlung[ab-1]) < 0) {
austausch = true; fertig = ab;
final E temp = sammlung[ab-1];
sammlung[ab-1]=sammlung[ab]; sammlung[ab]=temp;
}
links = fertig + 1;
for (int auf = links; auf <= rechts; auf++) // aufwärts
if (sammlung[auf].compareTo(sammlung[auf-1]) < 0) {
austausch = true; fertig = auf;
final E temp = sammlung[auf-1];
sammlung[auf-1] = sammlung[auf]; sammlung[auf] = temp;
}
rechts = fertig - 1;
} while (austausch);
}
Für alle Elemente wird nacheinander der Platz gefunden, wohin sie eingefügt werden sollen. Das Einfügen findet durch Verschiebung aller Elemente statt. Das Verfahren ist häufig schneller als Shaker Sort, die Zeitkomplexität ist jedoch immer noch n2.
Beispiel in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static <E extends Comparable<E>> void straightInsertion(E[] sammlung) { for (int index = 1; index < sammlung.length; index++) { // anfangen beim 2. Element final E elementZumEinfuegen = sammlung[index]; int einfuegestelle = index;
while (einfuegestelle > 0 &&
elementZumEinfuegen.compareTo(sammlung[einfuegestelle-1]) < 0) {
sammlung[einfuegestelle] = sammlung[einfuegestelle-1];
// nach oben schieben
einfuegestelle --;
}; // Einfügestelle gefunden: entweder weil einfuegestelle = 0, oder
// weil !elementZumEinfuegen.compareTo(sammlung[einfuegestelle - 1]) < 0
sammlung[einfuegestelle] = elementZumEinfuegen;
}
}
Die Elemente der Reihung werden nacheinander mit dem kleinsten unsortierten Element ausgetauscht. Die Zeitkomplexität ist n2
Visualisierung in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static <E extends Comparable<E>> void straightSelection(E[] sammlung) { for (int index = 0; index < sammlung.length-1; index++) { // bis zum vorletzten Element int austauschstelle = index; E elementZumAustauschen = sammlung[index];
for (int kleinstes = index + 1; kleinstes < sammlung.length; kleinstes++) {
if (sammlung[kleinstes].compareTo(elementZumAustauschen) < 0) {
austauschstelle = kleinstes; // index merken
elementZumAustauschen = sammlung[kleinstes];
}; // Austauschstelle gefunden
}
if (austauschstelle != index) { // Austausch nötig
sammlung[austauschstelle] = sammlung[index];
sammlung[index] = elementZumAustauschen;
}
}
}
Bei Straight Insertion wandern die Elemente in Einserschritten auf ihren endgültigen Platz. In dieser verbesserten Version führen sie größere Sprünge durch; die Entfernungen werden in einer Hilfsreihung schrittweiten angegeben. Diese müssen abnehmen und der letzte Wert muss 1 sein, damit die Reihung zum Schluss garantiert sortiert wird. Bei geeigneten Schrittweiten (z.B. …, 31, 15, 7, 3, 1) kann eine Zeitkomplexität von
erreicht werden (s. Donald E. Knuth: The Art of Computer Programming).
Beispiel in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static <E extends Comparable<E>> void shellSort(E[] sammlung, final int[] schrittweiten) { for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite for (int index = schrittweite; index < sammlung.length; index++){ E elementZumEinfuegen = sammlung[index]; int einfuegestelle = index; while (einfuegestelle - schrittweite >= 0 && elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) { sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite]; einfuegestelle -= schrittweite; // Sprung um schrittweite } sammlung[einfuegestelle] = elementZumEinfuegen; } } }
Die Strategie "teile und herrsche" ermöglicht eine Zeitkomplexität von n log n zum Preis des erhöhten Speicherkomplexität von log n: Die Abarbeitung der Rekursion erfordert Speicher im Stack.
Visualisierung in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static class QuickSort<E extends Comparable<E>> { private void sort(E[] sammlung, int links, int rechts) { int auf = links; // linke Grenze int ab = rechts; // rechte Grenze final E ausgewaehlt = sammlung[(links + rechts) / 2]; // ausgewähltes Element
do {
while (sammlung[auf].compareTo(ausgewaehlt) < 0)
auf ++; // suchen größeres Element von links an
while (ausgewaehlt.compareTo(sammlung[ab]) < 0)
ab --; // suchen kleineres Element von rechts an
if (auf <= ab) { // austauschen auf und ab:
final E temp = sammlung[auf];
sammlung[auf] = sammlung[ab];
sammlung[ab] = temp;
auf ++; // linke und rechte Grenze verschieben:
ab --;
};
} while (auf <= ab); // Überschneidung
if (links < ab)
sort(sammlung, links, ab); // linke Hälfte sortieren
if (auf < rechts)
sort(sammlung, auf, rechts); // rechte Hälfte sortieren
}
public void quickSort(E[] sammlung) {
sort(sammlung, 0, sammlung.length-1); // die ganze Reihung sortieren
}
}
Aufrufe:
QuickSort<Character>.quickSort(reihung); // s. reihung // im Gegensatz zu generischen Methoden muss der aktuelle Typparameter (hier: Character) für generische Klassen explizit angegeben werden QuickSort<Kunde>.quickSort(kundenkartei); // aktueller Typparameter ist Kunde
Der beste Sortieralgorithmus mit konstanter Speicherkomplexität und einer Zeitkomplexität von n log n ist der am meisten komplizierte. Er ahmt einen Binärbaum in der zu sortierenden Reihung durch Manipulierung der Indizes nach. Hierbei sind die zwei Nachfolger (im Sinne des Binärbaums) eines Elements mit dem Index i die beiden Elemente mit den Indizes 2i und 2i+1. Falls diese außerhalb der Reihungsgrenzen fallen, hat das Element keine Nachfolger (ist ein Blatt). Die Halde (heap) ist ein Abschnitt der Reihung (zwischen zwei Indizes), die die Haldenbedingung erfüllt. Im Heap Sort wird durch Austausch von Elementen zuerst eine Halde (von hinten nach vorne) aufgebaut und dann (von vorne nach hinten) abgebaut, indem die Spitze der Halde (das größte Element) mit dem hintersten ausgetauscht wird.
Visualisierung in Wikipedia
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ static class HeapSort<E extends Comparable<E>> { /* die Sequenz innerhalb von sammlung zwischen a und b erfüllt die Haldenbedingung, wenn für jedes i mit 2*i+1 <= b gilt (sofern 2*i und 2*i+1< sammlung.length-1): sammlung[i] > sammlung[2*i] && sammlung[i] > sammlung[2*i+1] */
private void senken(E[] sammlung, int links, int rechts) {
/* Die Halde zwischen links und rechts wird durch das Senken
des Elements sammlung[links - 1] nach unten erweitert:
Die Elemente zwischen links - 1 und rechts bilden eine Halde */
int index = links - 1; // linke Grenze der neuen Halde
int nachfolger = 2 * index; // linker Nachfolger
final E zuSenken = sammlung[index];
while (true) { // zwei Abbruchstellen
if (nachfolger > rechts) break; // weil kein Nachfolger
if (nachfolger < rechts &&
sammlung[nachfolger].compareTo(sammlung[nachfolger + 1]) < 0)
// kleineren nachfolger oder nachfolger + 1 auswählen
nachfolger ++;
if (sammlung[nachfolger].compareTo(zuSenken) < 0) break;
// weil Platz gefunden
sammlung[index] = sammlung[nachfolger]; // hochrücken
index = nachfolger; // nach unten gehen
nachfolger = 2 * index; // linker Nachfolger, wenn existiert
};
sammlung[index] = zuSenken; // Element einfügen
}
public void heapSort(E[] sammlung) { // sammlung[0] ungenutzt
/* Halde aufbauen; die obere Hälfte zwischen sammlung.length/2+1 und
sammlung.length-1 erfüllt die Haldenbedingung immer: */
int rechts = sammlung.length-1;
for (int links = rechts / 2 + 1; links > 1; links--)
// untere Hälfte einzeln hinzufügen
senken(sammlung, links, rechts);
// Elemente zwischen 1 und sammlung.length-1 erfüllen die Bedingung
// Halde wird abgebaut, d.h. sammlung wird sortiert:
final int links = 1; // sammlung[0] ungenutzt
for (rechts = sammlung.length-1; rechts > links; rechts--) {
// austauschen der äußeren Elemente:
final E groesstesElement = sammlung[links]; // Spitze
sammlung[links] = sammlung[rechts];
// hinteres Element nach vorne eintauschen
sammlung[rechts] = groesstesElement; // Element nach hinten
senken(sammlung, links + 1, rechts - 1); // Element senken
}
}
}
Zwei vorsortierte Sequenzen werden in eine neue sortierte gemischt. Die Sequenzen werden von zwei Iterator-Objekten geliefert und von einem Collection-Objekt aufgenommen. Iterator und Collection sind generische Standardklassen des Pakets java.util.
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ <E extends Comparable<E>> void merge(Iterator<E> eingabe1, Iterator<E> eingabe2, Collection<E> ausgabe) { // import java.util.Iterator, Collection // vorsortierte Sequenzen (geliefert von Iteratoren) werden gemischt // requires eingabe1.hasNext() && eingabe2.hasNext(); // Voraussetzung: die Sequenzen sind nicht leer E element1 = eingabe1.next(), element2 = eingabe2.next();
while (eingabe1.hasNext() && eingabe2.hasNext()) {
if (element1.compareTo(element2) < 0) {
ausgabe.add(element1); // das kleinere Element ausgeben
element1 = eingabe1.next(); // ein neues Element einlesen
}
else { // symmetrisch: eingabe1.next().compareTo(eingabe2.next()) >= 0
ausgabe.add(element2);
element2 = eingabe2.next();
}
} // eine der Eingabedateien ist erschöpft, Rest kopieren:
while (eingabe1.hasNext()) {
ausgabe.add(eingabe1.next());
eingabe1.next();
}
while (eingabe2.hasNext()) {
ausgabe.add(eingabe2.next());
eingabe2.next();
} // eine der beiden Schleifen ist leer
}
Aufruf:
class Eingabedatei implements Iterable<Kunde> { ... } // s. Kunde // Hier muss die Funktion iterator() implementiert werden, die ein java.util.Iterator<Element>-Objekt liefert. // Seine Methode next() liefert die vorsortierten Kunde-Objekte, wobei Kunde implements Comparable<Kunde>
class Ausgabedatei implements Collection<Kunde> { ... } // Hier muss die Methode add(Kunde) programmiert werden, die ein Kunde-Objekt in die Datei schreibt. // Die anderen Collection-Methoden können leer (dummy) implementiert werden.
Eingabedatei erste = new Kundendatei(), zweite = new Kundendatei(); Ausgabedatei dritte = new Ausgabedatei();
merge(erste.iterator(), zweite.iterator(), ausgabedatei); // Typparameter ist implizit Kunde
Eine Hash-Tabelle speichert Elemente zusammen mit einem Schlüssel, um sie später mit Hilfe ihres Schlüssels sehr schnell wieder finden zu können.
Die Sondierungsfunktion verkörpert die Strategie, wie Plätze in der Hash-Tabelle besetzt werden. Die lineare ist die einfachste, führt jedoch oft zu "Klumpen", in denen das Wiederauffinden langsam werden kann.
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 */ public class HashTabelle<Element, Schluessel> { // (einfachste) Hashtabelle mit linearer Sondierungsfunktion (in der Methode vorhanden) und ohne Verkettung private static class Eintrag<E, S> { // Tabelleneintrag /* Normalerweise sind innere Klassen von generischen Klassen implizit generisch, mit den selben Typparameter wie die äußere Klasse. Hier ist explizite Generizität nötig, um im Konstruktor ein Reihungsobjekt vom rohen Typ erzeugen zu können. */ E element; S schluessel; boolean belegt; // leere Einträge enthalten hier false }
private Eintrag<Element, Schluessel>[] tabelle; // die eigentliche Hashtabelle
private int anzahl; // der eingetragenen Elemente, anfänglich 0
public HashTabelle(int groesse) {
tabelle = new Eintrag[groesse]; // Reihungsobjekt kann nur vom rohen Typ erzeugt werden.
for (int i = 0; i < tabelle.length; i++) {
tabelle[i] = new Eintrag<Element, Schluessel>();
tabelle[i].belegt = false;
}
anzahl = 0;
}
private int index; // wird von vorhanden() beschrieben (Nebeneffekt!); von eintragen, suchen und vorhanden gelesen
public boolean vorhanden(Schluessel schluessel) {
index = schluessel.hashCode() % tabelle.length; // Nebeneffekt!
while (tabelle[index].belegt && schluessel != tabelle[index].schluessel)
index = (index + 1) % tabelle.length; // lineare Sondierungsfunktion
// Platz gefunden:
if (schluessel == tabelle[index].schluessel) // index zeigt auf den Platz, wo der letzte Schluessel steht
return true;
else // ! inhalt[index].belegt, index zeigt auf einen freien Platz
return false;
}
/** ein Element mit vorhandenem Schlüssel wird überschrieben (kein Doppeleintrag) */
public void eintragen(Schluessel schluessel, Element element) throws VollException {
if (anzahl == tabelle.length)
throw new VollException();
else if (! vorhanden(schluessel)) { // Nebeneffekt: vorhanden() hat index auf einen freien Platz positioniert
// neu eintragen, da ! vorhanden():
tabelle[index].schluessel = schluessel;
tabelle[index].belegt = true;
anzahl++;
}
tabelle[index].element = element; // wenn vorhanden(), dann wird überschreiben
}
public Element suchen(Schluessel schluessel) throws NichtVorhandenException {
if (! vorhanden(schluessel)) // Nebeneffekt: vorhanden() hat index positioniert
throw new NichtVorhandenException();
else // vorhanden hat index auf den Platz von schluessel positioniert
return tabelle[index].element;
}
}
class
VollException extends Exception { }
class
NichtVorhandenException extends
Exception { }
Die Menge der Schlüssel bestimmt die optimale Sondierungsfunktion. Der Benutzer im Kenntnis seiner Schlüssel kann eine bessere als die lineare programmieren.
/** Autor: Prof. Dr. Andreas Solymosi, (c) 2007 HashTabelle mit Sondierungsfunktion (als Delegat) */
public class HashTabelleSond<Element, Schluessel> {
/** Sondierungsfunktion muss vom Benutzer implementiert werden */
public static interface Sondierung { // in C# würde dies mit einem Delegat gelöst werden
/** Die Sondierungsfunktion liefert bei jedem Aufruf den nächsten Index zum Sondieren
* Wenn die Sondierungsfunktion nicht alle Tabellenplätze abtastet, kann eintragen() VollException werfen,
* auch wenn es in der Tabelle noch freie Plätze gibt. */
int sondierung(final int index); // z.B. lineare Sondierung: return index + 1
}
private class Eintrag<E, S> { // Tabelleneintrag
E element;
S schluessel;
boolean besucht; // wird von suchen() für Markierung benutzt
}
private Eintrag<Element, Schluessel>[] tabelle; // die eigentliche Hashtabelle
private Sondierung sondierung; // wird vom Benutzer als Konstruktorparameter übergeben
/** Konstruktorparameter sind Tabellengröße und Delegat */ public HashTabelleSond(final int groesse, final Sondierung sondierung) { tabelle = new Eintrag[groesse]; // Reihungsobjekt kann nur vom rohen Typ erzeugt werden. for (int i = 0; i < tabelle.length; i++) tabelle[i] = new Eintrag<Element, Schluessel>(); this.sondierung = sondierung; }
private int index; // mutable
// wird von der const-Methode suchen() beschrieben (Nebeneffekt!); von eintragen, suchen und vorhanden gelesen
/** Das Ergebnis der Suchfunktion ist null, wenn schluessel in der Tabelle nicht gefunden wurde. * Die Variable index wird auf den gefundenen Schlüssel oder auf einen freien Platz positioniert */ public Element suchen(final Schluessel schluessel) { // const index = schluessel.hashCode() % tabelle.length; // erster Versuch for (int i = 0; i < tabelle.length; i++) // besucht-Felder zurücksetzen, um Endlossuche zu unterbinden tabelle[i].besucht = false; while (schluessel != tabelle[index].schluessel) { if (tabelle[index].besucht) return null; // index schon besucht, schluessel nicht gefunden tabelle[index].besucht = true; // Endlossuche unterbinden index = sondierung.sondierung(index); // weiter sondieren } // index wurde auf schluessel oder auf einen freien Platz positioniert return tabelle[index].element; // null, wenn tabelle[index].schluessel == null }
/** besagt, ob schluessel in der Hashtabelle vorhanden ist */
public boolean vorhanden(final Schluessel schluessel) { // const
return suchen(schluessel) != null;
}
/** löscht evtl. vorhandenen Eintrag mit schluessel aus der Hashtabelle */
public void loeschen(final Schluessel schluessel) { // ensures !vorhanden(schluessel)
if (vorhanden(schluessel)) // suchen() positioniert index auf schluessel
tabelle[index].schluessel = tabelle[index].schluessel = null; // Tabellenplatz freigeben
}
/** element und schluessel werden in die Tabelle eingetragen.
* Wenn schluessel schon vorhanden ist, wird er überschrieben.
* Wenn die Eintragung nicht stattfinden kann (z.B. weil die Tabelle voll ist), wir VollException geworfen.
* Wenn die Sondierungsfunktion nicht alle Tabellenplätze abtastet, kann VollException geworfen werden,
* auch wenn es in der Tabelle noch freie Plätze gibt. */
public void eintragen(final Schluessel schluessel, final Element element) throws VollException {
if (!vorhanden(schluessel)) { // suchen() positioniert index auf schluessel oder auf einen freien Platz
if (tabelle[index].schluessel != null) // kein Platz wurde gefunden
throw new VollException();
tabelle[index].schluessel = schluessel;
}
// wenn !vorhanden(), dann eintragen; wenn vorhanden(), dann überschreiben (kein Doppeleintrag):
tabelle[index].element = element;
}
}
Instanziierung:
final HashTabelle<String, Integer> hashTabelle = new HashTabelle<String, Integer>(tabellengroesse, new HashTabelle.Sondierung() { public int sondierung(final int schluessel) { return (schluessel + 1) % tabellengroesse; } }); // der zweite Konstruktorparameter ist eine anonyme Implementierung der (inneren) Schnittstelle Sondierung
// jetzt können Paare von String und Integer in hashTabelle eingetragen, und dort gesucht werden, z.B.: hashTabelle.eintragen(6, "sechs"); System.out.println(hashTabelle.suchen(6)); // "sechs"
Version von 28.03.2016