Algorithmen

Zeitkomplexität von Algorithmen

Ziel ist immer die effiziente Ausführung von Algorithmen in einer minimalen Zeit, mit einem minimalen Aufwand (Ausführungsaufwand).

Der Ausführungsaufwand ist zu unterscheiden vom Aufwand den Algorithmus zu entwickeln, dem Entwicklungsaufwand. Langsame Anwendungen sind leider oft das Resultat von Implementierungen bei denen die Kostengründe für den Entwicklungsaufwand zu einem höheren Ausführungsaufwand führen...

Ausführungsaufwand versus Entwicklunggaufwand

Der Ausführungsaufwand hängt von vielen Faktoren ab. Viele Faktoren beruhen auf den unbekannten Komponenten des Ausführungssystems:

Die verlässlichste Art und Weise zur Beurteilung der Zeiteffizienz von Algorithmen ist die Abschätzung der Anzahl der Verarbeitungsschritte in Abhängigkeit von der Anzahl der Daten die zu verarbeiten sind.

Definition
Ordnung "O" eines Algorithmus
Die funktionale Abhängigkeit (bzw. Proportionalität) zwischen der Zahl der Ausführungsprogrammschritte und der Zahl (n) der zu verarbeitenden Datenelemente

Beispiele

Hierdurch ergeben sich verschiedene Kategorien von Problemen:

Praktisch ausführbare Algorithmen

Algorithmen die auch bei einer sehr viel größeren Zahl von Elementen in einer akzeptablen Zeit ausgeführt werden können.

Dies sind im Idealfall: O(n), O(log n), O (n*log n)

Man zählt hierzu aber auch Algorithmen mit einer polynomialen Ordnung wie O(n2) oder O(n3).

Praktisch nicht mehr ausführbare Algorithmen

Praktisch nicht mehr ausführbare Algorithmen lassen sich nicht in akzeptabler Zeit bei größer werdenden Datenbeständen ausführen. Dies sind Algorithmen mit einer exponentiellen Ordnung. O(xn). Hierzu zählt auch das Problem des Handlungsreisenden mit einer Ordnung von O(n!).

Rechenregeln für die Aufwandsbestimmung

Die Rechenregeln für die Aufwände von Algorithmen erlauben dem Entwickler die Komplexitätsklasse eine Algorithmus abzuschätzen.

Hierzu geht der Entwickler in zwei Schritten vor:

  1. Man bestimmt die Anzahl der auszuführenden Befehle eine Algorithmus in Abhängigkeit von den zu verarbeitenden Datenelementen n
  2. Man vereinfacht den Term mit dem Gesamtaufwand derart, dass der Term und jeder Teilterm in der gleichen Komplexitätsklasse bleibt

Am Ende bleibt dann ein einfacher Ausdruck für die Komplexitätsklasse übrig.

Klassen von Komplexität

  • konstant: O(1)
  • logarithmisch: O(log(n))
  • linear: O(n)
  • jenseits von linear: O(n*log(n))
  • polynomial: O(n2), O(n3), O(n4) etc.
  • exponentiell: O(kn)

Rechenregeln für einfache Betrachtungen

Gegeben sei eine Funktion f(n) mit dem Aufwand O(n). n sei die variable Anzahl der zu verarbeitenden Datenelemente

  • Konstanten: Konstanten haben keinen Einfluss:
    • O(f(n)+k) = O(f(n))+k = O(f(n)) für k konstant
    • O(f(n)*k)=O(f(n))*k = O(f(n)) für k konstant
    • O(k) = O(1)
    • konstante Aufwände werden nicht einberechnet. Dies gilt für Multiplikation, sowie für die Addition.
  • Nacheinander ausgeführte Funktion f und g
    • Der Aufwand O(f(n)) sei größer als der Aufwand von O(g(n))
    • O(f(n)+g(n))=O(f(n))+O(g(n)) = O(f(n))
    • ... der größere Aufwand gewinnt.
  • Ineinander geschachtelte Funktionen oder Programmteile wie Schleifen f(g(n))
    • O(f(g(n))) = O(f(n))*O(g(n))
    • der Aufwand multipliziert sich.
    • Einschränkung: Hier wird davon ausgegangen, dass beide Schleifen von der gleichen Variablen abhängen!

Weitere Informationen

Suchalgorithmen

Motivationsbild zum Suchen

Such- und Sortiervorgänge sind sehr häufige Aufgaben die in Anwendungen gelöst werden müssen.

Suchen ist ein Vorgang der komplementär zum Sortieren ist. Datenbestände die vollständig oder teilweise sortiert sind, lassen sich wesentlich einfacher durchsuchen. Ungeordnete Datenbestände lassen sich lassen sich im schlechtesten Fall nur linear durchsuchen.

Suchvorgänge lassen wie folgt kategorisieren:

  • Suchkriterium: Das gesuchte Objekt (Datum) unterscheidet sich durch eine eindeutiges Merkmal von allen anderen Daten. Das Merkmal kann aus einem einzelnen Attribut oder mehreren Attribute bestehen. Das Merkmal wird auch als Suchschlüssel bezeichnet.
  • Suchauftrag: Die Suche eines bestimmten Datums in einer Menge von Daten.
  • Suchziel: Der Zugriff auf das gesuchte Datum (Objekt).

Internes und externes Suchen

Man unterscheidet zwischen Suchvorgängen bei denen man den gesamten Datenbestand im Hauptspeicher verwalten kann (internes Suchen) und Suchvorgängen bei denen der Datenbestand nur teilweise in den Hauptspeicher geladen werden kann(externes Suchen).

Beim externen Suchen muss man also einen schnellen, aber begrenzten Hauptspeicher geschickt einsetzen um einen langsamen, aber kostengünstigeren Massenspeicher zu durchsuchen.

Die Unterscheidung zwischen den beiden Suchverfahren ist sehr wichtig für produktiv eingesetzte Anwendungen, in der Berechung der Zeitaufwände ist sie nicht hilfreich!

Ein Festplattenspeicher mag etwa 1000 mal langsamer als der Hauptspeicher eines Rechners sein. Dies macht bei einer echten Anwendung einen großen Unterschied. Bei der Berechnung der Zeitkomplexität wird dieser Faktor jedoch als "unbedeutend" weggekürzt.

Suchverfahren

Sequentielle Suche (lineare Suche)

 Die sequentielle Suche beruht auf dem naiven Ansatz einen Datenbestand vollständig zu durchsuchen bis das passende Element gefunden wird. Dieses Verfahren nennt man auch erschöpfende Suche oder im englischen das Greedy-Schema (engl. für gefräßig). Der Algorithmus für das Durchsuchen eines Felds ist der folgende:

  1. Spezifiziere Suchschlüssel
  2. Vergleiche jedes Element mit dem Suchschlüssel
    1. Erfolgsfall: Liefere Indexposition beim ersten Auffinden des Objekts und beende das Suchen
    2. Kein Erfolg: Gehe zum nächsten Objekt und vergleiche es.
  3. Gib eine Meldung über das erfolglose Suchen zurück wenn das Ende des Datenbestands erreicht wurde ohne das, das Objekt gefunden wird. Dies kann eine java-Ausnahme sein oder ein spezieller Rückgabewert (z.Bsp .1)

Der Aufwand für diesen Algorithmus ist linear, also O(n). Die Anzahl der nötigen Vergleichsoperationen hängt direkt von der Anzahl der Elemente im Datenbestand ab. Im statischen Mittel sind dies n/2 Vergleiche.

Sequentielle Suche in einem unsortierten Datenbestand

In diesem Fall muss bei jeder Suche der gesamte Datenbestand durchlaufen werden bis ein Element gefunden wurde

Beispiel einer Javaimplementierung

Die Methode sequentielleSuche() durchsucht ein Feld von 32 Bit Ganzzahlen nach einem vorgegebenen Schlüssel schluessel und gibt den Wert -1 zurück wenn kein Ergebnis gefunden wird.

public static int sequentielleSuche() (int[] feld, int schluessel) {
   int suchIndex = 0;
      while (suchIndex< feld.length && feld[suchIndex] != schluessel) suchIndex++;
      if (suchIndex == feld.length) suchindex = -1; // Nichts gefunden
   return suchindex;
}

Sequentielle Suche in einem sortierten Datenbestand

Bei einem sortierten Datenbestand kann man die Suche optimieren in dem man sie abbricht so bald man weiß, das die folgenden Elemente alle größer bzw. kleiner als das gesucht Element sind. Man muss also nicht das Feld vollständig durchlaufen. Hierdurch lässt sich Zeit sparen. Der durchschnittliche Aufwand von n/2 bleibt jedoch ein linearer Aufwand.

Beispiel einer Javaimplementierung

Die Methode sequentielleSuche() durchsucht ein Feld von 32 Bit Ganzzahlen nach einem vorgegebenen Schlüssel schluessel und gibt den Wert  -1 zurück wenn kein Ergebnis gefunden wird.

public static int sequentielleSuche() (int[] feld, int schluessel)
   int suchIndex = 0;
   while (suchIndex< feld.length && feld[suchIndex] < schluessel) suchIndex++;
      if ((suchindex < feld.length) && (feld[suchIndex] == feld[schluessel])) 
           return suchindex; // Erfolg
      else return -1; //kein Erfolg
}

Binäre Suche

Die binäre Suche erfolgt nach dem "Teile und Herrsche" Prinzip (divide et impera) durch Teilen der zu durchsuchenden Liste.

Voraussetzung: Die Folge muss steigend oder fallend sortiert sein!

Der Algorithmus lässt sich sehr gut rekursiv beschreiben:

Suche in einer sortierten Liste L nach einem Schlüssel k:

  • Beende die Suche erfolglos wenn die Liste leer ist
  • Nimm das Element auf der mittleren Position m der Liste und Vergleiche es mit dem Schlüssel
    • Falls der Schlüssel k kleiner als dasElement L[m] is (k<L[m]) durchsuche die linke Teilliste bis zum Element L[m]
    • Falls der Schlüssel k größer als dasElement L[m] is (k>L[m]) durchsuche die rechte Teilliste vom Element L[m] bis zum Ende
    • Beende die Suche wenn der Schlüssel k gleich L[m] ist (k=L[m])

Das binäre Suchen ist ein Standardverfahren der Informatik da es sehr effizient ist. Der Aufwand beträgt selbst im ungünstigsten Fall O(N)=log2(N).

Im günstigsten Fall ist der Aufwand O(N)=1 da eventuell der gesuchte Schlüssel sofort gefunden wird.

Beispiel einer binären Suche

Das folgende Feld hat 12 Elemente zwischen 1 und 23. Es wird ein Element mit dem Wert 15 gesucht. Zu Beginn ist das Suchintervall das gesamte Feld von Position 0 (links) bis 11 (rechts). Der Vergleichswert (mitte) wird aus dem arithmetischen Mittel der Intervallgrenzen berechnet.

Beispielimplementierung in Java

Die Methode binaerSuche() sucht einen Kandidaten in einem aufsteigend sortierten Feld von Ganzzahlen. Das Hauptprogramm erzeugt ein Feld mit der Größe 200 und aufsteigenden Werten

public class Binaersuche {
int[] feld; /** * * @param feld: Das zu durchsuchende Feld * @param links: linker Index des Intervalls * @param rechts: rechter Index des Intervalls * @param kandidat: der zu suchende Wert */

static void binaerSuche(int[] feld, int links,int rechts, int kandidat) {
int mitte;
do{
System.out.println("Intervall [" + links +
"," + rechts + "]");

mitte = (rechts + links) / 2;
if(feld[mitte] < kandidat){
links = mitte + 1;
} else {
rechts = mitte - 1;
}
} while(feld[mitte] != kandidat && links <= rechts);
if(feld[mitte]== kandidat){
System.out.println("Position: " + mitte);
} else {
System.out.println("Wert nicht vorhanden!");
}
}


public static void main(String[] args) {
int groesse=200;
int[] feld = new int[groesse];
for (int i=0; i<feld.length;i++)
feld[i] = 2*i; //Feld besteht aus geraden Zahlen
System.out.println("Suche feld["+ 66 + "]=" + feld[66]);
binaerSuche(feld, 0,(feld.length-1), feld[66]);
}
}

Programmausgabe auf Konsole:

Suche feld[66]=132
Intervall [0,199]
Intervall [0,98]
Intervall [50,98]
Intervall [50,73]
Intervall [62,73]
Intervall [62,66]
Intervall [65,66]
Intervall [66,66]
Position: 66

Weiterführe Quellen und Beispiele

Beispielanwendung zum Suchen

 Das folgende Programm zeigt eine sequentielle und eine binäre Suche in einem Feld mit zufälligen Werten.

Die Variable groesse erlaubt es die Größe des Felds zu verändern. Mit dem Nanotimer werden die benötigten Zeiten gemessen. Vergleichen Sie die Zeitaufwände für das sequentielle und das binäre Suchen mit dem Zeitaufwand für das Sortieren mit der Hilfklasse Arrays!

package s2.sort;
import java.util.Arrays;
/**
*
* @author sschneid
* @version 1.0
*/
public class Suchen {
public static int[] feld;
public static int groesse = 10000000;
/**
* Hauptprogramm
* @param args
*/
public static void main(String[] args) {
erzeugeFeld();
int suchwert =feld[groesse-2];
System.out.println("Suche feld["+ (groesse-2) +"] = " + suchwert);
sucheSequentiell(suchwert);
sortiere();
binaereSucheSelbst(suchwert);
binaereSuche(suchwert);

}
/**
* Erzeuge ein Feld mit Zufallszahlen
*/
public static void erzeugeFeld() {
feld = new int[groesse];
for (int i=0; i<feld.length;i++) {
feld[i]=(int)(Math.random() * (double)Integer.MAX_VALUE);
}
System.out.println("Feld mit "+ groesse + " Elementen erzeugt.");
}
/**
* Suche sequentiell einen Wert in einem unsortierten Feld
* @param suchwert der gesuchte Wert
*/
public static void sucheSequentiell(int suchwert) {
System.out.println("Sequentielle Suche nach Schlüssel");
long t = System.nanoTime();
int i=0;
while ( (i<groesse) && (suchwert != feld[i])) i++;
t = (System.nanoTime() -t)/1000000;
if (i== groesse) {
System.out.println(" Der Wert: " + suchwert +
" wurde nicht gefunden");
}
else {
System.out.println(" Der Suchwert wurde auf Position " + i +
" gefunden");
}
System.out.println(" Dauer sequentielle Suche: " + t +"ms");
}
/**
* Sortiere ein Feld mit der Klasse Arrays und messe die Zeit
* @param suchwert der gesuchte Wert
*/
public static void sortiere() {
System.out.println("Sortieren mit Arrays.sort()");
long t = System.nanoTime();
Arrays.sort(feld);
t = (System.nanoTime() -t)/1000000;
System.out.println(" Feld sortiert in " + t +" ms");
}
/**
* Suche binär einen Wert in einem sortierten Feld
* @param suchwert der gesuchte Wert
*/
public static void binaereSucheSelbst(int suchwert) {
System.out.println("Selbstimplementierte binäre Suche");
long t = System.nanoTime();
int intervall = (feld.length+1)/2;
int pos = intervall;
while ((intervall > 1) && (feld[pos] != suchwert)) {
intervall =(intervall+1)/2;
if ((feld[pos] > suchwert)) {pos -= intervall;}
else {pos += intervall;}
}
t = (System.nanoTime() -t);
if (feld[pos]== suchwert) {
System.out.println(" Der Suchwert wurde auf Position " +
pos +" gefunden");
}
else {
System.out.println(" Der Wert: " + suchwert +
" wurde nicht gefunden");
}
System.out.println(" Dauer binäre Suche " + (t/1000000) +"ms" +
" (" + t + " ns)");
}
/**
* Suche binär einen Wert in einem sortierten Feld
* Nutze die binäre Suchmethode der Klasse Arrays
* @param suchwert der gesuchte Wert
*/
public static void binaereSuche(int suchwert) {
System.out.println("Binäre Suche mit Arrays.binarySearch()");
long t = System.nanoTime();
int pos = Arrays.binarySearch(feld, suchwert);
t = (System.nanoTime() -t);
System.out.println(" Der Suchwert wurde auf Position " +
pos +" gefunden");
System.out.println(" Dauer binäre Suche " + (t/1000000) +
"ms" + " (" + t + " ns)");
}

}

Klasse in github.

Typische Konsolenausgabe:

Feld mit 10000000 Elementen erzeugt.
Suche feld[9999998] = 1719676120
Sequentielle Suche nach Schlüssel
Der Suchwert wurde auf Position 9999998 gefunden
Dauer sequentielle Suche: 28ms
Sortieren mit Arrays.sort()
Feld sortiert in 1296 ms
Selbstimplementierte binäre Suche
Der Suchwert wurde auf Position 8008593 gefunden
Dauer binäre Suche 0ms (6000 ns)
Binäre Suche mit Arrays.binarySearch()
Der Suchwert wurde auf Position 8008593 gefunden
Dauer binäre Suche 0ms (11000 ns)

 

Sortieralgorithmen

In diesem Abschnitt gehen wir davon aus, dass die zu sortierenden Datensätze in einem Feld f der Größe N in aufsteigender Reihenfolge sortiert werden. Die Feldelemente sollen in aufsteigender Reihenfolge sortiert werden.

Das Feld f dient als Eingabe für die Folge des Sortierverfahrens sowie als Ausgabedatenstruktur. Die Elemente müssen also innerhalb des Folge umsortiert werden. Nach dem Sortieren gilt für das Feld f:

f[1].wert <= f[2].wert ...<=f[N].wert

Beispiel

Unsortierte Folge mit N=7 Elementen:

Sortierte Folge mit N=7 Elementen

Bewertungskriterien

Bei der Bewertung der der Sortieralgorithmen wird jeweils in Abhängigkeit der Größe des zu sortierenden Feldes

  • die Anzahl der Schlüsselvergleiche C (englisch comparisons) und
  • die Anzahl der Bewegungen M (englisch: movements) der Elemente

gemessen.

Bei diesen zwei Parametern interessieren

  • der beste Fall (die wenigsten Operationen)
  • der schlechteste Fall (die meisten Operationen)
  • der durchschnittliche Fall

Schlüsselvergleiche sowie Bewegungen tragen beide zur Gesamtlaufzeit bei. Man wählt den größeren der beiden Werte um eine Abschätzung für die Gesamtlaufzeit zu erlangen.

Stabilität von Sortierverfahren

Ein weiteres Kriterium für die Bewertung von Sortiervorgängen ist die Stabilität.

Definition: Stabiles Sortierverfahren
Ein Sortierverfahren ist stabil wenn nach dem Sortieren die relative Ordnung von Datensätzen mit dem gleichen Sortierschlüssel erhalten bleibt.

Beispiel: Eine Folge von Personen die ursprünglich nach der Mitarbeiternummer (id) sortiert. Diese Folge soll mit dem Nachnamen als Sortierschlüssel sortiert werden.

Im folgenden Beispiel wurde ein stabiles Sortierverfahren angewendet. Die relative Ordnung der beiden Personen mit dem Namen "Schmidt" bleibt erhalten. Der Mitarbeiter mit der Nummer 18 bleibt vor dem Mitarbeiter mit der Nummer 21. 

Bei nicht stabilen Sortierverfahren bleibt diese relative Ordnung nicht unbedingt erhalten. Hier könnte eine sortierte Folge so aussehen:

nicht stabiles Sortierverfahren

Stabile Sortierverfahren erlauben das Sortieren nach mehreren Prioritäten da eine Vorsortierung erhalten wird.

Im oben gezeigten Beispiel kann man eine Folge

  • primär nach Nachnamen sortierten und
  • sekundär nach der Personalnummer (id).

Man sortiert die Personen zuerst nach dem Kriterium mit der niedrigen Priorität. Dies ist hier die Personalnummer. Diese Vorsortierung war schon gegeben. Anschließend sortiert man nach dem wichtigeren Kriterium, dem Nachnamen. Die so entstandene Folge ist primär nach Nachnamen sortieret, sekundär nach Personalnummer.

Beispielprogramme

 Die folgenden Beispielprogramme erlauben das Testen von unterschiedlichen Sortieralgorithmen.

Hinweis: Die Implementierungen der Sortieralgorithmen selbst sind in den Abschnitten der Algorithmen zu finden. Im Hauptprogramm MainSort kann man durch Instanziieren einen Sortieralgorithmus wählen.

Arbeitsanweisung

Kopieren, Bauen und Starten der Referenzimplementierung

  1. Legen Sie in Ihrer Entwicklungsumgebung das Paket s2.sort an
  2. Kopieren Sie die Quellen der unten aufgeführten Klassen (inklusive Trivialsort) in Ihre Entwicklungsumgebung. Achten Sie darauf, daß alle Klassen im Paket s2.sort angelegt werden.
  3. Übersetzen Sie alle Klassen
  4. Starten Sie Anwendung durch Aufruf der Klasse s2.sort.MainSort

Auf der Kommandozeile geschieht das mit dem Befehl

$ java s2.sort.MainSort

Die Konsolenausgabe dieser Anwendung ist:

Phase 1: Einfacher Test mit 6 Elementen
Algorithmus: Sortiere drei Werte
Unsortiert:
feld[0]=6
feld[1]=2
feld[2]=4
feld[3]=3
feld[4]=5
feld[5]=7
Zeit(ms): 0 Vergleiche: 2 Vertauschungen: 2. Fehler in Sortierung
Sortiert:
feld[0]=2
feld[1]=4
feld[2]=6
feld[3]=3
feld[4]=5
feld[5]=7
Keine Phase 2 (Stresstest) aufgrund von Fehlern...

Der Trivialsort hat leider nur die Schlüssel auf der Position 0 und 1 sortiert.

Effizienz des Algorithmus messen

Das Hauptprogramm MainSort wird bei einer korrekten Sortierung eines Testfelds mit 6 Werten automatisch in die zweite Phase eintreten.

Hier wird es ein Feld mit 5 Werten und Zufallsbelegungen Generieren und Sortieren.

Die Feldgröße wird dann automatisch verdoppelt und es wird eine neue Sortierung mit neuen Zufallswerten durchgeführt. Dies wird solange wiederholt bis ein Sortiervorgang eine voreingestellte Maximalzeit (3 Sekunden) überschritten hat.

Mit Hilfe dieser Variante kann man die benötigte Zeit pro Anzahl sortierter Elemente beobachten und die Effizienz des gewählten Algorithmus abschätzen.

Beim Sortieren durch Auswahl ergibt die die folgende Konsolenausgabe:

Phase 1: Einfacher Test mit 6 Elementen
Algorithmus: Sortieren durch Auswahl
Unsortiert:
feld[0]=6
feld[1]=2
feld[2]=4
feld[3]=3
feld[4]=5
feld[5]=7
Zeit(ms): 0 Vergleiche: 15 Vertauschungen: 5. Korrekt sortiert
Sortiert:
feld[0]=2
feld[1]=3
feld[2]=4
feld[3]=5
feld[4]=6
feld[5]=7
Phase 2: Stresstest
Der Stresstest wird beendet nachdem mehr als 3 Sekunden benötigt werden.
Maximalzeit(s): 3
Sortieren durch Auswahl. Feldgroesse: 10 Zeit(ms): 0 Vergleiche: 45 Vertauschungen: 9. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 20 Zeit(ms): 0 Vergleiche: 190 Vertauschungen: 19. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 40 Zeit(ms): 0 Vergleiche: 780 Vertauschungen: 39. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 80 Zeit(ms): 1 Vergleiche: 3160 Vertauschungen: 79. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 160 Zeit(ms): 5 Vergleiche: 12720 Vertauschungen: 159. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 320 Zeit(ms): 14 Vergleiche: 51040 Vertauschungen: 319. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 640 Zeit(ms): 14 Vergleiche: 204480 Vertauschungen: 639. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 1280 Zeit(ms): 19 Vergleiche: 818560 Vertauschungen: 1279. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 2560 Zeit(ms): 26 Vergleiche: 3275520 Vertauschungen: 2559. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 5120 Zeit(ms): 84 Vergleiche: 13104640 Vertauschungen: 5119. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 10240 Zeit(ms): 575 Vergleiche: 52423680 Vertauschungen: 10239. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 20480 Zeit(ms): 1814 Vergleiche: 209704960 Vertauschungen: 20479. Korrekt sortiert

Warnung

  • Diese zweite Phase funktioniert nicht mit dem Trivialsort. Hier werden nur zwei Vergleiche und zwei Vertauschnungen durchgeführtImplementieren der eigenen Algorithmen

 Nutzen Sie die vorgebenen Klassen zum Testender  eigener Algorithmen

  • Erzeugen Sie eine eigene Klasse für den Sortieralgorithmus
    • Sie können die Klasse TrivialSort übernehmen.
      • Ändern Sie den Klassennamen
      • Ändern Sie in der Methode algorithmus() den Namen des Algorithmus
      • Implementieren Sie die Methode sortieren(int von, int bis) die ein bestimmtes Intervall der Folge sortiert
  • Ändern Sie in der Klasse MainSort in der Methode algorithmusWahl() den benutzten Algorithmus.
  • Tipps: Nutzen Sie die Infrastruktur der Oberklasse Sortierer beim Testen
    • istKleiner(int a, int b), istKleinerGleich(int a, int b) : Vergleichen Sie die Werte des Feldes indem Sie bei diesen beiden Methoden den jeweiligen Index angeben. Es wird ein Zähler gepflegt der die Anzahl der gesamten Vergleiche beim Sortiervorgang zählt!
    • tausche(int i, int j): tauscht die Werte auf Index i mit dem Wert von Index j. Es wird ein Zähler gepflegt der die Anzahl der Vertauschungen zählt
    • tZaehler(): Inkrementiert die Anzahl der Vertauschungen falls nicht die Methode tausche() verwendet wurde. Dieser Zähler ist multi-threading (mt) save!
    • vglZaehler(): Inkrementiert die Anzahl der Vergleiche falls nicht die Methoden istKleiner() oder istKleinerGleich() verwendet werden. Dieser Zähler ist mt-save!
    • druckenKonsole() : druckt das Feld in seiner aktuellen Sortierung aus.
    • Tracing: Ihre Klasse mit dem Sortieralgorithmus erbt eine statische boolsche Variable geschwaetzig. Sie können diese Variable jederzeit setzem mit geschwaetzig=true. Es werden alle Vertauschungen und Vergleiche auf der Konsole ausgegeben:

Beim TrivialSort führt das Setzen dieser Variable zur folgenden Konsolenausgabe:

Phase 1: Einfacher Test mit 6 Elementen
Algorithmus: Sortiere drei Werte
Unsortiert:
feld[0]=6
feld[1]=2
feld[2]=4
feld[3]=3
feld[4]=5
feld[5]=7
Vergleich:feld[1]<feld[0] bzw. 2<6
Getauscht:feld[0<->1];f[0]=2;feld[1]=6
Vergleich:feld[2]<feld[1] bzw. 4<6
Getauscht:feld[1<->2];f[1]=4;feld[2]=6

Zeit(ms): 0 Vergleiche: 2 Vertauschungen: 2. Fehler in Sortierung
Sortiert:
feld[0]=2
feld[1]=4
feld[2]=6
feld[3]=3
feld[4]=5
feld[5]=7
Keine Phase 2 (Stresstest) aufgrund von Fehlern...

 

MainSort.java: Ein Testprogramm

Klasse MainSort.java

Warnung: Diese Klasse lädt die Algorithmen dynamisch. Sie funktioniert nur wenn

  • Die Namen der Klassen beibehalten werden. Die Namen der Klassen werden als Zeichenkette angegeben. Die Namen müssen vorhanden sein und die Klasse muss übersetzt worden sein.
  • Das Paket s2.sort bleibt. Wenn die Paketstruktur geändert wird muss auch die fett gedruckte Zeichenkette angepasst werden.
package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class MainSort { private static String algorithmusName;
/**
*
* Das Hauptprogramm sortiert sechs Zahlen in Phase 1
* Phase 2 wird nur aufgerufen wenn der Sortieralgorithmus
* für die erste Phase korrekt war
* @param args
*/
public static void main(String[] args) { if (args.length > 0)
algorithmusName = args[0];
else
algorithmusName="";
int zeit = 3;
System.out.println("Phase 1: Einfacher Test mit 6 Elementen");
boolean erfolg = phase1();
if (erfolg) {
System.out.println ("Phase 2: Stresstest");
System.out.print("Der Stresstest wird beendet nachdem mehr ");
System.out.println("als " + zeit + " Sekunden benötigt werden.");
phase2(zeit);
}
else {System.out.println("Keine Phase 2 (Stresstest) " +
"aufgrund von Fehlern...");}
}
/**
* Auswahl des Sortieralgorithmus
* @ param das zu sortierende Feld
* @ return der Sortieralgorithmus
*/
public static Sortierer algorithmusWahl(int[] feld) {
Sortierer sort= null;
// Wähle ein Sortieralgorithmus abhängig von der
// gewünschten Implementierung
String nameSortierKlasse;
if (algorithmusName.equals("")) {
algorithmusName = "TrivialSort";
//algorithmusName = "SelectionSort";
//algorithmusName = "InsertionSort";
//algorithmusName = "BubbleSort";
//algorithmusName = "QuickSort";
//algorithmusName = "QuickSortParallel";
}

Class<?> meineKlasse;
Constructor<?> konstruktor;

try {
// Dynamisches Aufrufen einer Klasse
// Hole Metainformation über Klasse
meineKlasse = Class.forName("s2.sort."+ algorithmusName);
// Hole alle Konstruktoren
Constructor[] konstruktoren = meineKlasse.getConstructors();
// Nimm den Ersten. Es sollte nure einen geben
konstruktor = konstruktoren[0];
// Erzeuge eine Instanz dynamisch
sort = (Sortierer) konstruktor.newInstance((Object)feld); } catch (ClassNotFoundException ex) { System.out.println("Klasse nicht gefunden. Scotty beam me up"); } catch (InstantiationException ex) { System.out.println("Probleme beim Instantieren. Scotty beam me up"); } catch (IllegalAccessException ex) { System.out.println("Probleme beim Zugriff. Scotty beam me up"); } catch (SecurityException ex) { System.out.println("Sicherheitsprobleme. Scotty beam me up"); } catch (IllegalArgumentException ex) { System.out.println("Falsches Argument. Scotty beam me up"); } catch (InvocationTargetException ex) { System.out.println("Falsches Ziel. Scotty beam me up"); } //sort.geschwaetzig = true; }

/**
* Sortiere 6 Zahlen
* @return wurde die Folge korrekt sortiert?
*/
public static boolean phase1() {
long anfangszeit = 0;
long t = 0;
int[] gz = new int[6];
gz[0] = 6;
gz[1] = 2;
gz[2] = 4;
gz[3] = 3;
gz[4] = 5;
gz[5] = 7;
Sortierer sort = algorithmusWahl(gz);
System.out.println("Algorithmus: " + sort.algorithmus());
System.out.println("Unsortiert:");
sort.druckenKonsole();
anfangszeit = System.nanoTime();
sort.sortieren(0, gz.length - 1);
t = System.nanoTime() - anfangszeit;
System.out.print(
" Zeit(ms): " + t / 1000000
+ " Vergleiche: " + sort.anzahlVergleiche()
+ " Vertauschungen: " + sort.anzahlVertauschungen());
boolean erfolg = sort.validierung();
if (erfolg) {System.out.println(". Korrekt sortiert");}
else {System.out.println(". Fehler in Sortierung");}
System.out.println("Sortiert:");
sort.druckenKonsole();
return erfolg;
}
/**
* Sortieren von zufallsgenerierten Feldern bis eine maximale
* Zeit pro Sortiervorgang in Sekunden erreicht ist
* @param maxTime
*/
public static void phase2(int maxTime) {
// Maximale Laufzeit in Nanosekunden
long maxTimeNano = (long) maxTime * 1000000000L;
long t = 0;
// Steigerungsfaktor für Anzahl der zu sortierenden Elemente
double steigerung = 2.0; // Faktor um dem das Feld vergrößert wird
int anzahl = 5; // Größe des initialen Felds
long anfangszeit;
int[] gz;
Sortierer sort;
System.out.println("Maximalzeit(s): " + maxTime);
while (t < maxTimeNano) {
// Sortiere bis das Zeitlimit erreicht ist
anzahl = (int) (anzahl * steigerung);
// Erzeugen eines neuen Feldes
gz = new int[anzahl];
for (int i = 0; i < gz.length; i++) {
gz[i] = 1;
}
sort = algorithmusWahl(gz);
sort.generiereZufallsbelegung();
sort.zaehlerRuecksetzen();
anfangszeit = System.nanoTime();
sort.sortieren(0, gz.length - 1);
t = System.nanoTime() - anfangszeit;
System.out.print(
sort.algorithmus() +
". Feldgroesse: " + anzahl + " Zeit(ms): " + t / 1000000 +
" Vergleiche: " + sort.anzahlVergleiche() +
" Vertauschungen: " + sort.anzahlVertauschungen());
if (sort.validierung()) {System.out.println(". Korrekt sortiert");}
else {System.out.println(". Fehler in Sortierung");}
sort.zaehlerRuecksetzen();
}
}
}

 Die Quellen bei github.

Sortierer.java

 Die Klasse Sortierer ist eine abstrakte Klasse die die Infrastruktur zum Sortieren zur Verfügung stellt.

  • Sie verwaltet ein Feld von ganzen Zahlen (int).
  • Sie stellt Operationen zum Vergleichen und Tauschen von Elementen zur Verfügung
  • Sie hat Zähler für durchgeführte Vertauschungen
  • Sie kann ein Feld auf korrekte Sortierung prüfen
  • Sie kann das Feld mit neuen Zufallszahlen belegen
  • Sie hat eine statische Variable geschwaetzig mit der man bei Bedarf jeden Vergleich und jede Vertauschung auf der Kommandozeile dokumentieren kann.
  • Die Klasse verwendete mt-sichere Zähler vom Typ AtomicInteger bei parallelen Algorithmen. Diese Zähler sind langsamer aber Sie garantieren ein atomares Inkrement.

Implementierung

package s2.sort;
import java.util.concurrent.atomic.AtomicInteger;
/**
*
* @author sschneid
* @version 2.1
*/
public abstract class Sortierer {
/**
* Das zu sortierende Feld
*/
protected int[] feld;
private int maxWert = Integer.MAX_VALUE;
// Zähler für serielle Sortieralgorithmen
private long tauschZaehlerSeriell;
private long vergleichszaehlerSeriell;
// Zähler für paralelle Sortieralgorithmen
private AtomicInteger tauschZaehlerParallel;
private AtomicInteger vergleichszaehlerParallel;
/**
* Der Algorithmus arbeitet parallel
*/
private final boolean parallel;
/**
* erweiterte Ausgaben beim Sortieren
*/
public static boolean geschwaetzig = false;
/**
* Initialisieren eines Sortierers mit einem
* unsortierten Eingabefeld s
* @param s ein unsortiertes Feld
* @param p der Algorithmus is parallel implementiert
*/
public Sortierer(int[] s, boolean p) {
feld = s;
parallel = p;
if (parallel) {
tauschZaehlerParallel = new AtomicInteger();
vergleichszaehlerParallel = new AtomicInteger();
}
else {
tauschZaehlerSeriell = 0;
vergleichszaehlerSeriell = 0;
}
}
/**
* die Groesse des zu sortierenden Feldes
*/
public int feldgroesse() {
return feld.length;
}
/**
* Gibt ein Feldelement auf gegebenem Index aus
* @param index
* @return
*/
public int getElement(int index) {
return feld[index];
}
/**
* sortiert das Eingabefeld
* @param s ein unsortiertes Feld
*/
abstract public void sortieren(int startIndex, int endeIndex);
/**
* Eine Referenz auf das Feld
* @return
*/
public int[] dasFeld() {
return feld;
}
/**
* kontrolliert ob ein Feld sortiert wurde
* @return
*/
public boolean validierung() {
boolean korrekt;
int i = 0;
while (((i + 1) < feld.length) &&
(feld[i]<=feld[i + 1])) {i++;}
korrekt = ((i + 1) == feld.length);
return korrekt;
}
/**
* Liefert den Namen des implementierten Sortieralgorithmus
* @return
*/
abstract public String algorithmus();
/**
* Drucken des Feldes auf System.out
*/
public void druckenKonsole() {
for (int i = 0; i < feld.length; i++) {
System.out.println("feld[" + i + "]=" + feld[i]);
}
}
/**
* Anzahl der Vertauschungen die zum Sortieren benoetigt wurden
* @return Anzahl der Vertauschungen
*/
public long anzahlVertauschungen() {
if (parallel) return tauschZaehlerParallel.get();
else return tauschZaehlerSeriell;
}
/**
* Anzahl der Vergleiche die zum Sortieren benoetigt wurden
* @return Anzahl der Vergleiche
*/
public long anzahlVergleiche() {
if (parallel) return vergleichszaehlerParallel.get();
else return vergleichszaehlerSeriell;
}
/**
* vergleicht zwei Zahlen a und b auf Größe
* @param a
* @param b
* @return wahr wenn a kleiner b ist
*/
public boolean istKleiner(int a, int b) {
vglZaehler();
if (geschwaetzig) {
System.out.println("Vergleich:feld["+a+"]<feld["+b+"] bzw. " +
feld[a] +"<"+ feld[b]);}
return (feld[a]<(feld[b]));
}
/**
* vergleicht zwei Zahlen a und b auf Größe
* @param a
* @param b
* @return wahr wenn a kleiner oder gleich b ist
*/
public boolean istKleinerGleich(int a, int b) {
vglZaehler();
if (geschwaetzig) {
System.out.println("Vergleich:feld["+a+"]<=feld["+b+"] bzw. " +
feld[a] +">"+ feld[b]);}
return (feld[a]<=(feld[b]));
}
/**
* diese Methode zaehlt alle Vergleiche. Sie ist mt-sicher
* für alle Algorithmen die das parallel Flag gesetzt haben
*/
public void vglZaehler() {
if (parallel) vergleichszaehlerParallel.getAndIncrement();
else vergleichszaehlerSeriell++;
}
/**
* Tausche den Inhalt der Position a mit dem Inhalt der Position b
* @param a
* @param b
*/
public void tausche(int a, int b) {
tZaehler();
if (geschwaetzig)
System.out.println("Getauscht:feld["+a+"<->"+b+"];f["+a
+ "]="+feld[b]+";feld["+b+"]="+feld[a]);
int s = feld[a];
feld[a] = feld[b];
feld[b] = s;
}
/**
* diese Methode zaehlt alle Vertauschungen. Sie ist mt-sicher
* für alle Algorithmen die das parallel Flag gesetzt haben
*/
public void tZaehler() {
if (parallel) tauschZaehlerParallel.getAndIncrement();
else tauschZaehlerSeriell++;
}
/**
* Belege das Feld mit Zufallswerten. Alte Belegungen werden gelöscht!
*/
public void generiereZufallsbelegung() {
// Generiere neue Belegung
maxWert = 2 * feld.length;
for (int i = 0; i < feld.length; i++) {
feld[i]=(int)(Math.random() * (double) maxWert);
}
}
/**
* Setzt Zaehler für Vertauschungen und Vergleiche zurueck auf Null
*/
public void zaehlerRuecksetzen() {
if (parallel) {
tauschZaehlerParallel.set(0);
vergleichszaehlerParallel.set(0);
}
else {
tauschZaehlerSeriell = 0;
vergleichszaehlerSeriell = 0;
}
}
}

 

TrivialSort.java

 Diese Klasse ist ein Platzhalter der nur die beiden ersten Elemente eines Intervalls sortieren kann.

Das Programm dient zum Testen des Beispiels und es zeigt den Einsatz der schon implementierten istKleiner() und tausche() Methoden die von der Oberklasse geerbt werden.

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class TrivialSort extends Sortierer{
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public TrivialSort(int[] s) { super(s,false); }
/**
* Diese Methode sortiert leider nur die beiden ersten Elemente
* auf der Position von und (von+1)
* @param von
* @param bis
*/
@Override
public void sortieren(int von, int bis) {
geschwaetzig = false;
int temp; // Zwischenspeicher
if (istKleiner(von+1,von)) {
tausche(von,von+1);
}
if (istKleiner(von+2,von+1)) {
tausche(von+1,von+2);
}
//druckenKonsole();
}
@Override
public String algorithmus() {
return "Sortiere drei Werte";
}
}

 

Sortieren durch Auswahl (Selection Sort)

Beim Suchen durch Auswahl durchsucht man das jeweilige Feld nach dem kleinsten Wert und tauscht den Wert an der gefundenen Position mit dem Wert an der ersten Stelle.

Anschließend sucht man ab der zweiten Position aufsteigend nach dem zweitkleinsten Wert und tauscht diesen Wert mit dem Wert der zweiten Position.

Man fährt entsprechend mit der dritten und allen weiteren Positionen fort bis alle Werte aufsteigend sortiert sind.

Verfahren

  • Man suche im Feld f[1] bis f[N] die Position i1 an der sich das Element mit dem kleinsten Schlüssel befindet und vertausche f[1] mit f[i1]
  • Man suche im Feld f[2] bis f[N] die Position i2 an der sich das Element mit dem kleinsten Schlüssel befindet und vertausche f[2] mit f[i2]
  • Man verfahre wie oben weiter für Position i3 bis iN-1

Beispiel

Ausgangssituation: Ein Feld mit 7 unsortierten Ganzzahlwerten (N=7)

Die Zahl 12 auf Position 5 ist die kleinste Zahl im Feld f[1] bis f[7]. Somit ist i1=5. Nach Vertauschen von f[1] mit f[5] ergibt sich:

Die Zahl 13 auf Position 4 ist die kleinste Zahl im Feld f[2] bis f[7]. Somit ist i2=4. Nach Vertauschen von f[2] mit f[4] ergibt sich:

Die Zahl 18 auf Position 5 ist die kleinste Zahl im Feld f[3] bis f[7]. Somit ist i3=5. Nach Vertauschen von f[3] mit f[5] ergibt sich:

Das Verfahren wird entsprechend weiter wiederholt bis alle Werte sortiert sind.

Aufwand

Der minimale Aufwand Mmin(N), der maximale Aufwand Mmax(N) und er mittlere Aufwand Mmit(N) ist bei diesem naiven Verfahren gleich, da immer die gleiche Anzahl von Operationen (N-1) ausgeführt wird. Der Faktor 3 ensteht dadurch, dass bei einer Vertauschung zweier Werte insgesamt drei Operationen braucht:

 

Die Anzahl der Vergleiche sind die Summe von n-1, n-1 etc. unabhängig davon ob das Feld sortiert oder unsortiert ist:

 

Selectionsort: Implementierung in Java

Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden ist.

Implementierung: Klasse Selectionsort

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class SelectionSort extends Sortierer{
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public SelectionSort(int[] s) {super(s,false);}
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
@Override
public void sortieren(int startIndex, int endeIndex){
//geschwaetzig=true;
int minimumIndex;
for (int unteresEnde=startIndex; unteresEnde<endeIndex; unteresEnde++) {
minimumIndex = unteresEnde; //Vergleichswert
// Bestimme Position des kleinsten Element im Intervall
for (int j=unteresEnde+1; j<=endeIndex; j++) {
if (istKleiner(j,minimumIndex)) {
minimumIndex=j; // neuer Kandidat
}
}
// Tausche kleinstes Element an den Anfang des Intervalls
tausche(unteresEnde,minimumIndex);
// das kleinste Element belegt jetzt das untere Ende des Intervalls
}
}
/**
* Liefert den Namen des SelectionSorts
* @return
*/
@Override
public String algorithmus() {return "Sortieren durch Auswahl";}
}

 

Sortieren durch Einfügen (Insertion Sort)

Verfahren

Das Sortieren durch Einfügen ist ein intuitives und elementare Verfahren:

  • Man teilt die zu sortierende Folge f mit N Elementen in eine bereits sortierte Teilfolge f[0] bis f[s-1] und in eine unsortierte Teilfolge f[s] bis f[n].
    • Zu Beginn ist die sortierte Teilfolge leer.
    • Der Beginn der unsortierten Folge f[s] wird die Sortiergrenze genannt.
  • Man setzt eine Sortiergrenze hinter der bereits durch Zufall sortierte Teilfolge f[1] bis f[s-1]
  • Vergleiche f[s] mit f[s-1] und vertausche die beiden Elemente falls f[s]<f[s-1]
    • Führe weitere Vergleiche und absteigende Vertauschungen durch bis man ein f[s-j] gefunden hat für das gilt f[s-j-1]<f[s-j]
  • Erhöhe die Sortiergrenze von f[i] auf f[i+1] und wiederhole die Vergleichs- und Vertauschungsschritte wie im vorhergehenden Schritt beschrieben.
  • Die Folge ist sortiert wenn die Sortiergrenze das Ende des Folge erreicht hat.

Beispiel

Initiale teilsortierte Folge Gegeben sei eine Folge in einem Feld mit sieben Elementen. Die ersten drei Elemente sind bereits sortiert und die Sortiergrenze wird mit 4 belegt. Die unsortierte Folge beginnt auf dem Feldindex vier.
Initiale teilsortierte Folge  Als erstes wird der Wert f[4]=20 mit f[3]=35 verglichen. Da f[4] größer als f[3] ist, werden die beiden Werte getauscht.
Initiale teilsortierte Folge Anschließend folgt der Vergleich von f[3]=20 mit f[2]=23. Der Wert von f[3] ist größer als f[2]. Die beiden Werte werden getauscht. 
Initiale teilsortierte Folge Der Vergleich von f[2] mit f[1] zeigt, dass f[2] größer als f[1] ist. f[2]=20 hat also seine korrekte Position in der sortierten Teilfolge gefunden.
Initiale teilsortierte Folge Der aktuelle Durchlauf ist hiermit beendet. Die Sortiergrenze wird um eins erhöht und erhält den Wert 5.
Initiale teilsortierte Folge Die sortierte Teilfolge ist um eins größer geworden. Es wird wieder f[5]=17 mit f[4]=35 verglichen. Da f[5] größer als f[4] ist, werden die beiden Werte getauscht. Jeder Durchlauf endet, wenn der Wert nicht mehr getauscht werden muss. Der Algorithmus endet wenn die Sortiergrenze die gesamt Folge umfasst.

 

Aufwand

Das Sortieren durch Einfügen braucht im günstigsten Fall nur N-1 Vergleiche für eine bereits sortierte Folge. Im ungünstigsten Fall (fallend sortiert) ist aber ein quadratisches Aufwand nötig.

Das gleiche gilt für die Vertauschungen. Hier müssen im ungünstigsten Fall Vertauschungen in einer quadratischen Größenordnung durchgeführt werden.

Insertionsort: Implementierung in Java

 Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse InsertionSort

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class InsertionSort extends Sortierer {
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public InsertionSort(int[] s) {
super(s,false);
}
/**
* sortiert ein Feld im Bereich startIndex bis endeIndex
* @param startIndex
* @param endeIndex
*/
public void sortieren(int startIndex, int endeIndex) {
for (int sortierGrenze = startIndex;sortierGrenze < endeIndex;
sortierGrenze++) {
int probe = sortierGrenze + 1;
int j = startIndex;
while (istKleiner(j, probe)) {
j++;
}
// Verschiebe alles nach rechts.
// Tausche den Probenwert gegen den unteren Nachbarn
// bis man bei der Position j angekommen ist
for (int k = probe - 1; k >= j; k--) {
tausche(k, k + 1);
}
}
}
/**
* Liefert den Namen des Insertion Sorts
* @return
*/
public String algorithmus() {
return "Sortieren durch Einfuegen";
}
}

Bubblesort

Der Bubblesort hat seinen Namen von dem Prinzip erhalten, dass der größte Wert eine Folge durch Vertauschungen in der Folge austeigt wie eine Luftblase im Wasser.

Verfahren

  • Vergleiche in aufsteigender Folge die Werte einer unsortierten Folge und vertausche die Werte wenn f(i) > f(i+1) ist
  • Wiederhole die Vergleiche und eventuell nötige Vertauschungen bis keine Vetauschung bei einem Prüfdurchlauf vorgenommen werden muss.

Beispiel

Es werden die Werte aufsteigen auf ihre korrekte Reihenfolge verglichen. Im ersten "Durchlauf" müssen die Werte 19 und 15 (in grau) getauscht werden. Anschließend werden die Werte 28 und 23 getauscht und im nächsten Schritt die Werte 28 und 17. Die letzte Vertauschung findet zwischen 28 auf Position 5 und 21 auf Position 6 statt. Der  erste Durchlauf ist beendet und der zweite Durchlauf beginnt mit den Vergleichen ab Index 1.
Im zweiten Durchlauf sind die Werte auf Index 1 und 2 in der richtigen Reihenfolge. Die Werte 23 und 17 sind die ersten die getauscht werden müssen. Der Wert 23 steigt weiter auf und wird noch mit dem Wert 21 getauscht. Die letzten beiden Werte auf Index 6 und 7 sind in der richtigen Reihenfolge und müssen nicht getauscht werden. Der zweite Durchlauf ist beendet.
Im dritten Durchlauf muß die 19 auf Position 2 mit der 17 auf Position 3 getauscht werden. Auf den höheren Positionen sind keine Veratuschungen mehr nötig.

Der vierte Durchlauf ist der letzte Durchlauf. In ihm finden keine weiteren Vertauschungen statt. Alle Elemente sind aufsteigend sortiert. Der Algorithmus bricht nach dem vierten Durchlauf ab, da keine Vertauschungen nötig waren. Alle Elemente sind sortiert.

Aufwand

Der günstigste Fall für den Bubblesort ist eine sortierte Folge. In diesem Fall müssen nur N-1 Vergleiche und keine Vertauschungen vorgenommen werden.

Ungünstige Fälle sind fallende Folgen. Findet man das kleinste Element auf dem höchsten Index sind N-1 Durchläufe nötigt bei denen das kleinste Element nur um eine Position nach vorne rückt. 

In ungünstigen Fällen ist der Aufwand N2. Man kann zeigen, dass der mittlere Aufwand bei N2 liegt:

Effizienzsteigerungen

Es gibt eine Reihe von Verbesserungen die darauf beruhen, dass man nicht bei jedem Durchlauf in der ganzen Folge die Nachbarn vergleichen muss. Nach dem ersten Durchlauf ist das größte Element auf dem Index N angekommen. Man muss im nächsten Durchlauf also nur noch alle Nachbarn bis zur Position N-1 kontrollieren.

BubbleSort: Implementierung in Java

 Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse BubbleSort

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class BubbleSort extends Sortierer {
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public BubbleSort(int[] s) {super(s, false); }
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
public void sortieren(int startIndex, int endeIndex) {
boolean vertauscht;
do {
vertauscht = false;
for (int i = startIndex; i+1 <= endeIndex; i++) {
if (istKleiner(i + 1,i)) {
tausche(i,i+1);
vertauscht = true;
}
}
} while (vertauscht);
}
/**
* Liefert den Namen des Bubble Sorts
* @return
*/
public String algorithmus() {
return "Bubble Sort";
}
}

 

Quicksort: Sortieren durch rekursives Teilen

Der Quicksort ist ein Verfahren welches auf dem Grundprinzip des rekursiven Teilens basiert:

  • Man nimmt ein beliebiges Pivotelement als Referenz (Pivotpunkt: Drehpunkt, Angelpunkt)
  • Man teilt die unsortierte Folge in drei Unterfolgen
    • Alle Elemente die kleiner oder gleich dem Pivotelement sind
    • Das Pivotelement
    • Alle Element die größer oder gleich dem Pivotelement sind

Die Unterfolgen die größer bzw. kleiner als das Pivotelement sind, sind selbst noch unsortiert. Das Pivotelement steht bereits an der richtigen Position zwischen den zwei Teilfolgen.

Durch rekursives Sortieren werden auch sie sortiert.

Der Quicksort wurde 1962 von C.A.R. Hoare (Computer Journal) veröffentlicht.

Verfahren

  • Folgen die aus keinem oder einem Element bestehen bleiben unverändert.
  • Wähle ein Pivotelement p der Folge F und teile die Folge in Teilfolgen F1 und F2 derart das gilt:
    • F1 enhält nur Elemente von F ohne das Pivotelement p die kleiner oder gleich p sind
    • F2 enhält nur Elemente von F ohne das Pivotelement p die größer oder gleich p sind
  • Die Folgen F1 und F2 werden rekursiv nach dem gleichen Prinzip sortiert
  • Die Ergebnis der Sortierung ist eine Aneinanderreihung der der Teilfolgen F1, p, F2.

Anmerkung: Der Quicksort folgt dem allgemeinen Prinzip von "Teile und herrsche" (lat.: "Divide et impera", engl. "Divide and conquer")

Beispiel

Im ersten Schritt wird das vollständige Feld vom Index 1 bis 7 sortiert, indem der Wert 23 auf dem Index 7 als  Pivotwert (Vergleichswert) gewählt.

Es wird nun vom linken Ende des Intervals (Index 1) aufsteigend das erste Element gesucht welches größer als das Pivotelement ist. Hier ist es der Wert 39 auf dem Index 2. Anschließend wird vom oberen Ende des Intervals von der Position links vom Pivotelement absteigend das erste Element gesucht welches kleiner als das Pivotelement ist. Hier ist es der Wert 19 auf dem Index 6.

Im nächsten Schritt werden die beiden gefundenen Werte getauscht und liegen nun in der "richtigen" Teilfolge.

Jetzt wird die Suche von links nach rechts weitergeführt bis das nächste Element gefunden ist welches größer als das Pivotelement ist. Hier ist es 35 auf Position 3. Die fallende Suche von Rechts endet bei dem Wert 17 auf Index 5. Die beiden Werte werden dann getauscht.

Nach der Vertauschung wird die aufsteigende Suche von Links weitergeführt und endet beim Wert 28 auf dem Index 4. Die fallende Suche von Rechts endet sofort da der Suchindex der steigenden Suche erreicht ist.

Der Pivotwert 23 auf Index 7 wird jetzt mit 28 auf dem Index  getauscht und hat seine korrekte Endposition erreicht.

Der Sortiervorgang wird jetzt rekursiv im Intervall 1 bis 3 und 5 bis 7 fortgeführt. Wie zuvor werden die Werte auf dem höchsten Index der Unterintervalle wieder als Pivotwerte gewählt.

Im linken Unterintervall endet die aufsteigende Suche schnell beim Wert 19 auf Index 2 der dann mit dem Pivotwert 17 getauscht wird. Im rechten Unterintervall muss bei der aufsteigenden suche der Wert 35 auf Index 5 mit dem Pivotwert 28 getauscht werden.

Bei den weiteren Teilungen in Unterintervalle bleiben nur noch das Intervall von Index 1 bis 2 sowie das Intervall von Index 6 bis 7 übrig. Hier werden wieder die Elemente am rechten Rand als Pivotwerte gewählt.

Im linken Unterintervall durchläuft die aufsteigende Suche das einzige Element und endet ohne Vertauschung. Im rechten Intervall muss ein letztes mal der Wert 39 mit 35 getauscht werden.

Aufwand

Der Quicksort ist in normalen Situationen mit einem Aufwand von n*log(n) sehr gut für große Datenmengen geeignet. Er ist einer der schnellsten Algorithmen. Bei sehr ungünstigen Sortierfolgen (schon sortiert) kann er aber auch mit einem quadratischen Aufwand sehr ineffizient sein.

Vorsortierte Folgen sind durchaus häufig bei realen Problemen zu finden. Der Quicksort ist bei schon sortierten Folgen sehr ineffizient ist und daher ist der Einsatz bei realen Anwendungen durchaus heikel.

 

Quicksort: Implementierung in Java

 Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse Quicksort

package s2.sort;
/**
*
* @author sschneid
*/
public class QuickSort extends Sortierer{
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public QuickSort(int[] s) {
super(s,false);
}
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
@Override
public void sortieren(int startIndex, int endeIndex) {
int i = startIndex;
int j = endeIndex;
int pivotWert = feld[startIndex+(endeIndex-startIndex)/2];
//System.out.println("von"+ startIndex+", bis:"+endeIndex +
// " pivot:" + pivotWert);
while (i<=j) {
// Suche vom unteren Ende des Bereichs aufsteigend einen
// Feldeintrag welcher groesser als das Pivotelement ist
while (feld[i] < pivotWert) {i++;vglZaehler();}
// Suche vom oberen Ende des Bereichs absteigend einen
// Feldeintrag der kleiner als das Pivotelement ist
while (feld[j] > pivotWert) {j--;vglZaehler();}
// Vertausche beide Werte falls die Zeiger sich nicht
// aufgrund mangelnden Erfolgs überschnitten haben
if (i<=j) {
tausche(i,j);
i++;
j--;
}
}
// Sortiere unteren Bereich
if (startIndex<j) {sortieren(startIndex,j);}
// Sortiere oberen Bereich
if (i<endeIndex) {sortieren(i,endeIndex);}
}
/**
* Liefert den Namen des Insertion Sorts
* @return
*/
@Override
public String algorithmus() {
return "QuickSort";
}
}
 

Implementierung: Parallelisierter Quicksort

Die unten aufgeführte Klasse nutzt die "Concurrency Utilities" die in Java 7 eingeführt wurden. Aus der Sammlung wird das Fork/Join Framework verwendet.

Das Aufteilen des Sortierintervalls erfolgt hier seriell in einer eigenen Methode.

Das Sortieren der Teilintervalle erfolgt parallel solange das Intervall eine bestimmte Mindestgröße (100) besitzt.

Die Fork/Join Klassen stellen dem Algorithmus einen Pool von Threads zur Verfügung die sich nach der Anzahl des Prozessoren des Rechners richten.

Hierzu dient eine Spezialisierung der Klasse RecursiveAction

  • Die Methode compute() wird in einem eigenen Thread durchgeführt wenn das dazugehörige Objekt mit der Methode invokeAll() aufgerufen wird. Diese Methode wird überschrieben.
  • Die Methode invokeAll() erlaubt es neue Tasks zu in Auftrag zu geben. Diese Methode wird erst beendet wenn alle Tasks ausgeführt sind.

In der vorliegenden Implementierung erfolgt ein paralleler Aufruf eines Task zum Sortieren der Teilintervalle und nicht ein sequentieller Methodenaufruf.

Die Implementierung des Task erfolgt in der inneren Klasse Sorttask. Diese Klasse ummantelt quasi die Sortiermethode.

package s2.sort;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
/**
*
* @author sschneid
* @version 2.0
*/
public class QuickSortParallel extends Sortierer{
static int SIZE_THRESHOLD=100; // Schwellwert für paralleles Sortieren
private static final ForkJoinPool THREADPOOL = new ForkJoinPool();
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist parallel (true Argument)
* @param s
*/public QuickSortParallel(int[] s) {
super(s, true);
}
/**
* Innere statische Klasse die Fork and Join aus dem Concurrency package
* implementiert. Sie macht aus Methodenaufrufen, Taskaufrufe von Threads
*/
static class SortTask extends RecursiveAction {
int lo, hi;
QuickSortParallel qsp;
/**
* Speichere alle wichtigen Parameter für den Task
* @param lo untere Intervallgrenze
* @param hi obere Intervallgrenze
* @param qsp Referenz auf das zu sortierende Objekt
*/
SortTask(int lo, int hi, QuickSortParallel qsp) {
this.lo = lo;
this.hi = hi;
this.qsp =qsp;
}
/**
* Führe Task in eigenem Thread aus und nutze Instanzvariablen
* als Parameter um Aufgabe auszuführen.
*/
@Override
protected void compute() {
//System.out.println(" Thread ID => " + Thread.currentThread().getId());
if (hi - lo < SIZE_THRESHOLD) {
// Sortiere kleine Intervalle seriell
qsp.sortierenSeriell(lo, hi);}
else { // Sortiere große Intervalle parallel
int obergrenzeLinkesIntervall;
obergrenzeLinkesIntervall = qsp.teilsortieren(lo,hi);
// der serielle rekursive Aufruf wird ersetzt durch
// den parallelen Aufruf zweier Threads aus dem Threadpool
//System.out.println("Parallel: "+
// lo+","+obergrenzeLinkesIntervall+","+hi);
invokeAll(new SortTask(lo,obergrenzeLinkesIntervall,qsp),
new SortTask(obergrenzeLinkesIntervall+1,hi,qsp));
}
}
}
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
@Override
public void sortieren(int startIndex, int endeIndex) {
THREADPOOL.invoke(new SortTask(startIndex,endeIndex,this));
}
/**
* sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
* zurück
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
public void sortierenSeriell(int startIndex, int endeIndex) {
if (endeIndex > startIndex) {
int obergrenzeLinkesIntervall= teilsortieren(startIndex, endeIndex);
//System.out.println("Seriell: "+
// startIndex+","+obergrenzeLinkesIntervall+","+endeIndex);
// Sortiere unteren Bereich
if (startIndex<obergrenzeLinkesIntervall) {
sortierenSeriell(startIndex,obergrenzeLinkesIntervall);}
// Sortiere oberen Bereich
if (obergrenzeLinkesIntervall+1<endeIndex) {
sortierenSeriell(obergrenzeLinkesIntervall+1,endeIndex);}
}
}
public int teilsortieren(int startIndex, int endeIndex) {
int i = startIndex;
int j = endeIndex;
int pivotWert = feld[startIndex+(endeIndex-startIndex)/2];
//druckenKonsole();
while (i<=j) {
// Suche vom unteren Ende des Bereichs aufsteigend einen
// Feldeintrag welcher groesser als das Pivotelement ist
while (feld[i] < pivotWert) {i++;vglZaehler();}
// Suche vom oberen Ende des Bereichs absteigend einen
// Feldeintrag der kleiner als das Pivotelement ist
while (feld[j]> pivotWert) {j--;vglZaehler();}
// Vertausche beide Werte falls die Zeiger sich nicht
// aufgrund mangelnden Erfolgs überschnitten haben
if (i<=j) {
tausche(i,j);
i++;
j--;
}
}
//System.out.println("von"+ startIndex+", bis:"+endeIndex +
// " pivot:" + pivotWert + " , return: " +i);
return i-1;
}
/**
* Liefert den Namen des Insertion Sorts
* @return
*/
public String algorithmus() {
return "QuickSort mit Fork and Join";
}
}
 

Hinweis: Dieser Algorithmus ist parallel. Er teilt dies der Oberklasse im Konstruktor als Parameter mit. Hierdurch werden die Zähler für die Vergleiche von Vertauschungen und Vergleichen vor einem parallelen Inkrement geschützt. Die Synchronisierung dieser Zählvariablen ist leider so aufwendig, dass der Algorithmus nicht mehr schneller als der seriell Algorithmus ist...

Man muss hier leider eine Entscheidung treffen:

  • setzen des Flag auf true: Die Vertauschungen werden korrekt gezählt. Der Algorithmus ist korrekt und langsam.
  • setzen des flag auf false: Die Veretauschungen und Vergleiche werden nicht korrekt gezählt. Der Algorithmus ist korrekt und schnell. Das bedeutet, er skaliert auf Mehrprozessorsystemen. 

 

Übung (Quicksort)

Führen Sie einen Durchlauf des Quicksorts manuell durch. Teilen Sie ein gegebenes Sortierintervall (Aufgabe: Vorher) nach den Regeln des Quicksorts in zwei Unterintervalle die noch sortiert werden müssen.

  • Sortieren Sie aufsteigend
  • Wählen Sie das Pivotelement ganz rechts im Intervall.
    • Markieren Sie das Pivotelement in der Aufgabe mit einem Pfeil von unten (siehe Beispiel).
  • Wenden Sie die Regeln des Quicksorts an. Zeichnen Sie zweiseitige Pfeile im "Vorher" Diagramm ein, um die notwendigen Vertauschungen zu markieren.
  • Zeichnen Sie mit einem zweiseitigen Pfeil die nötige Vertauschung des Pivotelements im "Vorher" Diagramm ein.
  • Tragen Sie alle neuen Werte im "Nachher" Diagramm ein.
  • Zeichnen sie die beiden verbliebenen zu sortierenden Zahlenintevalle mit eckigen Linien (siehe "Vorher" Diagramm) ein.

Lösung (Quicksort)

 

Heapsort

Der Heapsort (Sortieren mit einer Halde) ist eine Variante des Sortierens durch Auswahl. Er wurde in den 1960er Jahren von Robert W. Floyd und J. W. J. Williams entwickelt (siehe: Artikel in Wikipedia).

Der Heapsort hat den Vorteil, dass er auch im ungünstigsten Fall in der Lage ist mit einem Aufwand von O(N*log(N)) zu sortieren.

Hierfür wird eine Datenstruktur (der Heap) verwendet mit der die Bestimmung des Maximums einer Folge in einem Schritt möglich ist.

Heap und Feldrepräsentation

Beim Heapsort werden die zu sortierenden Schlüssel einer Folge in zwei Repräsentation betrachet:

  • Feldrepräsentation: Die Folge der unsortierten Schlüssel in einem Feld die sortiert werden soll. Am Ende des Heapsorts soll diese Folge als Feld aufsteigend sortiert sein.
  • Heaprepräsentation: Eine interne Repräsentation auf der die Regeln des Heapsorts angewendet werden. Diese Heaprepräsentation in der Form eines Binärbaums dient ausschließlich dem Verständnis des Betrachters

Beide Repräsentationen sind Sichten auf die gleichen Daten. Beim Heapsort werden nicht die Schlüssel in einen Binärbaum umkopiert. Die Heaprepräsentation dient nur dem Betrachter zur Verdeutlichung der Beziehung gewisser Feldpositionen.

Die Grundidee des Heapsorts besteht darin, daß an der Wurzel des Binärbaums immer der größte Schlüssel stehen muss. Diesen größten Schlüssel kann man dann dem Binärbaum entnehmen und als größtes Element der Folge benutzen. Die verbliebene unsortierte Teilfolge muss dann wieder so als ein Baum organisiert werden in dem das größte Element an der Wurzel steht. Durch sukzessives Entnehmen der verbliebenen gößten Elemente kann man die gesamte Folge sortieren.

Beim Heapsort muss nicht nur an der Wurzel des Baums der größte Schlüssel stehen. Jeder Knoten im Binärbaum muss größer als die Unterknoten sein. Diese Bedingung nennt man die Heapbedingung.

Verfahren

Beim Heapsort wird auf eine Feld mit N unsortierten Schlüsseln das folgende Verfahren wiederholt angewendet:

  • Herstellen der Heapbedingung  durch das Bootom-Up für ein Feld mit N Schlüsseln
  • Tauschen des ersten und größten Schlüssels auf der Position 1 mit dem letzten unsortierten Schlüssel auf Position N.
    • Wiederherstellen des Heapbedingung durch Versickern (Top-Down Verfahren)
  • Wiederholen des Verfahrens für die Positionen 1 bis N-1. Ab der Position N ist das Feld schon sortiert.

Beispiel

Grafische Visualisierung Beschreibung
Beispiel Heapkriterium

Das Beispiel links zeigt nicht eine vollständige Sortierung der gesamten Folge.

Es zeigt nur das Einsortieren eines Elements für eine Feldstruktur die schon der Heapbedingung genügt.

Das Feld mit den N=9 Elementen wurde so vorsortiert, dass es der Heapdebingung genügt. Das Herstellen der Heapbedingung wird später erläutert.

Beispiel Heapkriterium

Das Element mit dem Schlüssel 9 wird von der Spitze des Baums f[1] entfernt...

Beispiel Heapkriterium

... und mit dem Wert 2 der Position N=9 getauscht. Der größte Schlüssel der Folge befindet sich jetzt auf der Position 9.

Alle Elemente ab f[9]= F[N] aufwärts sind jetzt aufsteigend sortiert.

Alle Elemente von f[1] bis f[N-1]=f[8] sind unsortiert und müssen noch sortiert werden.

Die Elemente von f[1] bis f[8] genügen auch nicht mehr der Heapbedingung. Der Wert f[1]=2 ist nicht größer als f[2]=8 oder f[3]=7


Die Heapbedingung

Ein Feld f[1] bis f[N] mit Schlüsseln bildet einen Heap wenn die folgende Bedingung gilt:

Heapbedingung

f[i]<=f[i/2] für 2<= i <= N]
oder
f[i]>=f[2*i] und f[i]>=f[2*i+1] für 2*i<=N und 2*i+1<= N

Die Heapbedingung lässt sich leichter grafisch in einer Baumdarstellung verdeutlichen:

Beispiel Heapkriterium

Das Feld f mit der Feldgröße N=9

  • f[1] = 9
  • f[2] = 8
  • f[3] = 7
  • f[4] = 3
  • f[5] = 6
  • etc.

genügt der Heapbedingung da jeder obere Knoten größer als die beiden Unterknoten ist.

Die Position im Feld wird hier in rot dargestellt. Der Schlüssel (Wert) des Feldelements hat einen gelben Hintergrund

Herstellen der Heapbedingung für einen unsortierten Heap (Bottom-Up Methode)

Mit dem Bottom-Up Verfahren kann man die Heapbedingung für vollständig unsortierte Folgen von Schlüsseln herstellen.

Das Verfahren basiert auf der Idee, dass beginnend mit dem Schlüssel auf der höchsten Feldposition f[N] der Wert versickert wird um anschließend den nächst niedrigeren Wert F[N-1] zu versickern bis man den größten Wert f[1] versickert hat.

Beispiel

Grafische Visualisierung Beschreibung
Schritt 1

Der gegebene Baum sei vollständig mit Zufallsschlüsseln belegt. Alle Werte sind zufällig.

Die Positionen 5, 6,7,8 und 9 können nicht versickert werden, da sie keine Unterblattknoten zum Versickern haben.

Bottom Up Schritt 2 Das Bottom-Up Verfahren beginnt mit dem ersten Knoten i der über Unterknoten verfügt. Dieser Knoten ist immer die Position N/2 abgerundet. Bei N=9 ist die 9/2= 4.5. Der abgerundete Wert ist i=4. Hier muß f[8]=9 mit f[4]=3 getauscht werden um den Schlüssel zu versickern.
Bottom Up Schritt 3 Bei i=3 muss f[3]=4 mit f[7]=5 getauscht werden und ist damit auch versickert.
Bottom Up Schritt 4 Bei i=2 muss f[4] mit f[2] getauscht werden. Das rekursives Versickern bei f[4]=9 is nicht notwendig. f[4]=9 ist größer als f[8]=3 und f[9]=2 
Bottom Up Schritt 4

Bei i=1 muss f[1] mit  f[2]=9 getauscht werden.

 

Bottom Up Schritt 4 Nach dem Neubesetzen der Position f[2]=7 zeigt sich aber, dass die Heapbedingung für den entsprechenden Teilbaum von f[2] nicht gilt da f[2|<f[2*i+1] ist. f[2] muss also rekursiv weiter versickert werden. 
Bottom Up Schritt 4

Nach dem Tauschen von f[2]=7 mit f[5]=8 ist das rekursive Versickern beendet. f[5] hat keine Unterknoten da 5 > N/2 ist.

Der Baum genügt jetzt der Heapbedingung

 

Herstellen der Heapbedingung durch Versickern (Top-Down Methode)

Herstellen der Heapbedingung

Top-Down-Verfahren

Dieses Verfahren dient der Herstellen der Heapbedingung, wenn schon für die Unterheaps für die Heapbedingung gilt.

Man wendet es an, nachdem man den größten Schlüssel entnommen hat und ihn durch den Wert mit dem größten Index im unsortierten Baum ersetzt hat.

Das Versickern dieses neuen Schlüssels an der Wurzel des Baums erfolgt mit den folgenden Schritten:

  • Beginne mit der Position i=1 im Baum
  • Der Schlüssel f[i] hat keine Unterknoten da 2*i>N ist,
    • Der Schlüssel kann nicht mehr versickert werden. Das Verfahren ist beendet. 
  • Der Schlüssel f[i] hat noch genau einen Unterknoten f[i*2]
    • Der Schlüssel f[i] wird mit dem Schlüssel f[i*2] getauscht falls f[i]<f[i*2]. Das Verfahren ist nach diesem Schritt beendet.
  • Der Schlüssel f[i] hat noch Unterknoten f[2*i] und f[2*i+1]
    • Der Schlüssel f[i] ist der größte der drei Schlüssel f[i], f[i*2],f[i*2+1]
      • Das Verfahren ist beendet die Heapbedingung ist gegeben
    • Der Schlüssel f[i*2] ist der größte der drei Schlüssel f[i], f[i*2],f[i*2+1]
      • Tausche die Schlüssel f[i] mit f[2*i]
      • Versickere den Schlüssel f[i*2] nach dem Top-Down Verfahren
    • Der Schlüssel f[i*2+1] ist der größte der drei Schlüssel f[i], f[i*2],f[i*2+1]
      • Tausche die Schlüssel f[i] mit f[2*i+1]
      • Versickere den Schlüssel f[i*2+1] nach dem Top-Down Verfahren

Diese rekursive Verfahren wird hier an einem Beispiel gezeigt:

Grafische Visualisierung Beschreibung
Beispiel Heapkriterium

Durch das Entfernen des größten Schlüssels f[1] entstehen zwei Unterbäume für die die Heapbedingung nach wie vor gilt.

Beispiel Heapkriterium

Durch das Einsetzen eines Schlüssel von der Position N ist nicht mehr garantiert, dass die Heapbedingung für den gesamten Restbaum f[1] bis f[N-1]=f[8] gegeben ist.

Der Schlüssel f[1]=2 ist eventuell größer als die Schlüssel f[2*1] und f[2*1+1]. In diesem Fall ist die Heapbedingung für f[1] bis f[8] schon gegeben. Es muss nichts mehr getan werden.

Im vorliegenden Fall ist f[1]=2 aber nicht der größte Schlüssel. Er muss rekursiv versickert werden.

Dies geschieht durch das Vertauschen mit f[2] = 8. f[3] = 7 ist nicht der richtige Kandidat. 7 ist nicht der größte der drei Schlüssel.

Beispiel Heapkriterium

Nach dem Vertauschen von f[1] mit f[2] gilt die Heapbedingung zwar für den obersten Knoten. Sie gilt jedoch nicht für den Teilbaum unter f[2]= 2. Der Schlüssel 2 muss weiter versickert werden.

In diesem Fall ist f[5]=6 der größte Schlüssel mit dem f[2]= 2 vertauscht weden muss.

Beispiel Heapkriterium

Nach dem Vertauschen von f[2] mit f[5] gilt die Heapbedingung wieder für den gesamten Baum.

 

 

Heapsort: Implementierung in Java

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class HeapSort extends Sortierer{
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public HeapSort(int[] s) {super(s,false);}
/**
* sortiert ein Eingabefeld s
* @param s ein unsortiertes Feld
* @return ein sortiertes Feld
*/
public void sortieren(int startIndex, int endeIndex){
// Erzeugen der Heapbedingung, Bottom up...
for (int i=(endeIndex-1)/2; i>=0; i--) versickere (i,endeIndex);
//System.out.println("Heapbedingung hergestellt");
for (int i=endeIndex; i>0; i--) {
// Tausche das jeweils letzte Element mit dem Groeßten an der
// Wurzel. Versickere die neue Wurzel und verkürze
// das zu sortierende Intervall von hinten nach vorne
tausche(0,i); // Groesstes Element von der Wurzel an das Ende
// des Intervals getauscht
versickere(0,i-1); // versickere die neue Wurzel um Heapbedingung
// herzustellen
}
}
/**
* Berechne Index des linken Sohns für gegebenen Index
* liefere -1 zurück falls keine linker Sohn existiert
* @param index für den Sohn berechnet wird
* @param endeIndex letzter belegter Indexplatz
* @return
*/
private int linkerSohn(int index, int endeIndex) {
int ls = index*2+1;
if (ls > endeIndex)
return -1;
else return ls;
}
/**
* Berechne Index des linken Sohns für gegebenen Index
* liefere -1 zurück falls keine linker Sohn existiert
* @param index für den Sohn berechnet wird
* @param endeIndex letzter belegter Indexplatz
* @return
*/
private int rechterSohn(int index, int endeIndex) {
int rs = (index+1)*2;
if (rs > endeIndex)
return -1;
else return rs;
}
/**
* Versickere ein Element auf der Position "vers"
* @param vers Index des zu versickernden Elements
* @param endeIndex hoechste Indexposition die zum Verisckern zur Verfügung
* steht. Sie wird bei der Berechnung des rechts Sohns
* benötigt
*/
private void versickere (int vers, int endeIndex) {
int ls = linkerSohn(vers,endeIndex);
int rs = rechterSohn(vers,endeIndex);
int groessererSohn;
while (ls != -1) { // Es gibt einen linken Sohn
// Versickere bis Heapbedingung erfüllt ist oder keine
// Söhne mehr vorhanden sind
groessererSohn =ls; // linker Sohn als groesseren Sohn nominieren
if ((rs != -1) && (istKleiner(ls,rs))) groessererSohn = rs;
// der rechte Sohn existiert und war groesser...
if (istKleiner(vers,groessererSohn)) {
tausche(vers,groessererSohn); // beide Felder wurden getauscht
vers = groessererSohn;
ls = linkerSohn(vers,endeIndex);
rs = rechterSohn(vers,endeIndex);
}
else ls=-1; // Abbruchbedingung für while Schleife
}
}
/**
* Liefert den Namen des Heap Sorts
* @return
*/
public String algorithmus() {return "Heap Sort";}
}

 

Zusammenfassung

Aufwände der vorgestellten SortieralgorithmenO(N2)

  Cmin Caver Cmax Mmin Maver Mmax
Selectionsort O(N2) O(N2) O(N2) O(N) O(N) O(N)
Insertionsort O(N) O(N2) O(N2) O(N) O(N2) O(N2)
Bubblesort O(N) O(N2) O(N2) O(0) O(N2) O(N2)
Quicksort O(NlogN) O(NlogN) O(N2) O(0) O(NlogN) O(NlogN)
Heapsort* O(NlogN) O(NlogN) O(NlogN) O(NlogN) O(NlogN) O(NlogN)

* Der Heapsort ist ein nicht stabiles Sortierverfahren!

Bei der Betrachtung der Gesamtlaufzeit muss auch der Speicherplatzverbrauch berücksichtigt werden:

Gesamtlaufzeit
  Min Average Max Speicher
Selectionsort O(N2) O(N2) O(N2) O(1)
Insertionsort O(N) O(N2) O(N2) O(1)
Bubblesort O(N) O(N2) O(N2) O(1)
Quicksort O(NlogN) O(NlogN) O(N2) O(logN)
Heapsort O(NlogN) O(NlogN) O(NlogN) O(1)

Der Quicksort benötigt Speicherplatz der dem Logarithmus der zu sortierenden Anzahl der Werte abhängt. Die rekursiven Aufrufe benötigen zusätzlichen Platz zum Verwalten der Intervallgrenzen.

Übungen (Sortieren)

Teamübung: Analyse und Implementierung eines Sortieralgorithmus

Wählen Sie einen Algorithmus

  • recherchieren Sie seine Funktion
  • implementieren Sie den Algorithmus

1. Konfiguration der Laufzeitumgebung

Benutzen Sie die Beispielprogramme zum Sortieren:

  • Kopieren Sie sich die Klassen Sortierer, MainSort auf ihr System
  • Kopieren Sie sich die Klasse SelectionSort auf Ihr System
  • "Aktivieren" Sie sich den gewünschten Sortieralgorithmus in der Klasse MainSort, Methode algorithmusAuswahl(). Alle Sortieralgorithmen sind als Kommentarzeilen vorhanden. Das Entfernen genau eines Kommentar's aktiviert den gewünschten Algorithmus. Beginnen Sie zum Testen mit der Referenzimplementierung der Klasse SelectionSort.

Testen Sie die Gesamtanwendung durch das Aufrufen des Hauptprogramms MainSort.

In diesem Fall beginnt das Programm ein kleines Feld zu sortieren und gibt die Anzahl der Vergleiche, Vertauschungen, Größe des Feldes und die benötigte Zeit in Millisekunden aus. Dies ist die Phase 1. Wurde das kleine Feld erfolgreich sortiert beginnt Phase 2. Hier wird die Feldgröße jeweils verdoppelt. Das Programm bricht ab nachdem zum ersten Mal eine Zeitgrenze (3 Sekunden) beim Sortieren überschritten wurde. Hiermit lässt sich die Effizienz des Algorithmus testen und die Komplexitätsabschätzungen kontrollieren.

2. Implementieren Sie den neuen Sortieralgorithmus

Orientieren Sie sich am Beispiel der Klasse SelectionSort

  • Erzeugen Sie eine neue Klasse, die aus der Klasse Sortierer abgeleitet wird
  • Implementieren sie einen einfachen Konstruktor der das übergebene Feld an die Oberklasse Sortierer weiterreicht:
    • public XYSort(Sortierbar[] s) {super(s);}
  • Implementieren Sie eine Methode mit dem Namen algorithmus() die den Namen des Algorithmus ausgibt
    • public String algorithmus() {return "XYsort";}
  • Implementieren Sie den eigentlichen Sortieralgorithmus in der Methode public void sortieren(anfang, ende)
    • Diese Methode soll als Ergebnis alle Elemente von der Position anfang im Feld bis zum Feldelement ende aufsteigend sortiert haben.

 2.1 Infrastruktur für die Methode sortieren(anfang, ende)

Die Oberklasse Sortierer stellt alles zur Verfügung was man zum Sortieren benötigt

  • tausche(x,y) erlaubt das Tauschen zweier Feldelemente auf der Position x mit dem Element auf der Position y
  • boolean istKleiner(x,y) gibt den Wert true (wahr) zurück wenn der Inhalt der Feldposition x kleiner als der Inhalt der Feldposition y ist

Diese beiden Hilfsmethoden sind die einzigen Methoden die zum Implementieren benötigt werden. Der Typ des zu sortierenden Feldes bleibt hinter dem Interface Sortierbar verborgen. Im vorliegenden Fall sind es ganze Zahlen.

Um die Entwicklung zu Vereinfachen bietet die abstrakte Klasse Sortieren eine Reihe von Hilfsmethoden:

  • druckenKonsole(): druckt das gesamt Feld mit seiner Belegung auf der Konsole aus
  • generiereZufallsbelegung(): Belegt ein existierendes Feld mit neuen Testdaten 
  • long anzahlVertauschungen(): Gibt die Zahl der Vertauschungen an. Sie werden durch Aufrufe von tausche() gezählt
  • long anzahl Vergleiche(): Gibt die Zahl der Vergleiche aus. Sie werden durch Aufrufe von istKleiner() gezählt
  • boolean validierung(): Erlaubt die Prüfung eines sortierten Felds. Der Wert ist wahr wenn das Feld korrekt sortiert ist.

3. Anpassen des Hauptprogramms MainSort

Das Hauptprogramm MainSort erzeugt an einer Stelle eine Instanz der Klasse SelectionSort. Ändern Sie diese Stelle im Programm derart, dass eine Instanz Ihrer neuen Sortierklasse aufgerufen wird.

4. Vorbereitende Tests für die Präsentation

Ändern Sie die zu sortierenden Testdaten im Programm MainSort derart ab, dass Sie

  • den ungünstigsten Fall für den Sortieralgorithmus wählen (Vertauschungen, Prüfungen)
  • den günstigsten Fall wählen (Vertauschungen, Prüfungen)

Tragen Sie die abgelesen Werte in eine Tabellenkalkulation ein und prüfen Sie ob die Aufwände mit den Vorhersagen des Lehrbuchs übereinstimmen (Grafiken!)

Bereiten Sie eine 15-20 minütige Vorstellung/Präsentation des Algorithmus vor:

  • Erklären des Algorithmus (mit Beispiel)
    • Tafel, Folie, Overheadprojektor genügen
  • Vorführen einer Implementierung
  • Komplexitätsüberlegungen und Bewertung
    • Was ist der durchschnittliche Aufwand?
    • Was ist der minimale Aufwand (Beispiel)?
      • Wählen Sie die Anzahl der Vertauschungen oder der Vergleiche
    • Was ist der Aufwand im ungünstigsten Fall (Beispiel)?
      • Wählen Sie die Anzahl der Vertauschungen oder der Vergleiche
  • Wichtige Punkte die abhängig vom Algorithmus beachtet werden sollen
    • Sortieren durch Auswahl
      • Präsentation
        • Erklären Sie die "Sortiergrenze"
    • Bubblesort
      • Präsentation
        • Welche Elemente werden immer vertauscht?
        • Warum ist diese Strategie intuitiv aber nicht effizient?
    • Quicksort
      • Nutzen Sie Bleistifte oder Streichhölzer zum Visualieren des Verfahrens.
      • Legen Sie das Pivotelement in Ihrer Implementierung der Einfachheit halber an eine feste Intervallgrenze!
      • Algorithmus:
        • Erklären Sie das grundlegende Konzept des Quicksorts (3 Sätze reichen hier!)
        • Erklären Sie die Rekursion (Teile und Herrsche) und das Ende der Rekursion (Abbruch)
      • Implementierung
        • Erklären Sie den Begriff des "Pivotelement"
        • Die Implementierung ist durchaus kompliziert. Skizieren Sie sie nur.
    • Heapsort
      • Diskutieren Sie den Dualismus der beiden Zugriffstrukturen
        • Sie arbeiten auf einem Feld (Array)
        • Sie betrachten auf der abstrakten Ebene einen Baum
        • Wie ist der Zusammenhang zwischen Blattknoten und Feldpositionen?
      • Implementierung
        • Schreiben Sie Methoden zur Bestimmung der linken und rechten Blattknoten
        • Schreiben Sie eine Methode zum Versickern
      • Präsentation
        • Erläutern Sie den Dualismus
        • Erläutern Sie die Bestimmung der Blattknoten
        • Erläutern Sie die "Heapbedingung"
          • Wie wird sie hergestellt
        • Erläutern Sie das Konzept des "Versickerns" 
    • Referenzen aus dem Internet
      • Zeigen die Referenzen, die Sie am besten mögen: Lustig, lehrreich, witzig
    • Zusammenfassung:
      • Wie mögen Sie den Algorithmus?
      • Wie aufwendig war die Implementierung?

 

Backtracking

 Es gibt drei Arten von Backtracking:

  1. Entscheidungsproblem: Hier eine eine Lösung gesucht
  2. Optimierungsproblem: Hier wird die beste Lösung gesucht.
  3. Aufzählungsproblem: Hier werden alle Lösungen gesucht.

Welche Beispiele aus dem echten Leben gibt es für diese drei Kategorien?

Definition (nach Wikipedia)
Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, das heißt, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können (Prinzip des Ariadnefadens). Mit Backtracking-Algorithmen wird eine vorhandene Lösung entweder gefunden (unter Umständen nach sehr langer Laufzeit), oder es kann definitiv ausgesagt werden, dass keine Lösung existiert. Backtracking wird meistens am einfachsten rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion.

Zeitkomplexität (nach Wikipedia)

Bei der Tiefensuche werden bei maximal z möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von N im schlechtesten Fall 1+z+z2+z3+⋯+zN Knoten erweitert.

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit O(zN) und einem Verzweigungsgrad z>1 eine exponentielle Laufzeit. Je größer die Suchtiefe n, desto länger dauert die Suche nach einer Lösung. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet.

Resourcen

 

Teile und Herrsche Paradigma

Grundprinzip[ (nach Wikipedia)


Bei einem Teile-und-herrsche-Ansatz wird das eigentliche – in seiner Gesamtheit – als zu schwierig erscheinende Problem so lange rekursiv in kleinere und einfachere Teilprobleme zerlegt, bis diese gelöst („beherrschbar“) sind. Anschließend wird aus diesen Teillösungen eine Lösung für das Gesamtproblem (re-)konstruiert.

Resourcen

Lernziele

Am Ende dieses Blocks können Sie:

  • ... den Aufwand für einfache Algorithmen mit einem Parameter bestimmen
    • geschachtelte Schleifen mit dem gleichen Zähler
    • nacheinander ausgeführte Blöcke
  • ... Blöcke mit konstantem Aufwand erkennen
  • ... die vorgestellten Sortierverfahren erklären und auf kleine Folgen anwenden
  • ... den Aufwand für die vorgestellten Sortierverfahren abschätzen
  • .... stabile von nicht stabilen Sortierverfahren unterscheiden
  • ... Vor- und Nachteile der vorgestellten Sortierverfahren erläutern
  • ... eine Menge von Schlüsseln effizient sortieren.
  • ... für unterschiedliche Sortierprobleme die optimalen Suchalgorithmen auswählen und deren Vorteile erklären
  • ... die wichtigsten Kriterien zum Sortien, von zum Beispiel, 15 Bleistiften zu nennen.
  • ... für die vorgestellten Grundalgorithmen passende Beispiele nennen.

Feedback

Referenzen

T.Ottmann / P.Widmayer: Algorithmen und Datenstrukturen: Kapitel Sortieren

Lernzielkontrolle

Sie sind in der Lage die folgenden Fragen zu beantworten: Fragen zu Algorithmen