Lösungsvorschläge

zu den Aufgaben im Kapitel 5

Aufgabe 5.2: Welche sind „die wichtigsten Operationen“ bei jedem dieser Verfahren? Welchen Einfluss haben die Verbesserungen auf die Zeitkomplexität?

Lösung: Der Vergleich zweier Elemente und der Austausch zweier benachbarten Elemente. Die Verbesserung hat die Zeitkomplexität nicht verbessert, nur den Zeitverbrauch (um eine Konstante).

Aufgabe 5.3: Verbessern Sie die Prozedur straight insertion um das binäre Suchen, in dem die Suche nach der Einfügestelle in der Sequenz nicht sequenziell erfolgt, sondern nach der Strategie teile und herrsche.

Lösung:

private int suchen(Element[] sammlung, Element zumSuchen, int bis) {
   int links = 0; int rechts = bis;
   while (links < rechts) {
     int mitte = (links + rechts) / 2;
     if (zumSuchen.less(sammlung[mitte]))
      rechts = mitte-1;
     else
      links = mitte+1; }
   if (zumSuchen.less(sammlung[links]) && links > 0)
     links--;
   if (sammlung[links].less(zumSuchen))
     links++;
   return links; }

void straightInsertionBinary(Element[] sammlung) {
   for (int index = 1; index < sammlung.length; index++) {
     final Element elementZumEinfuegen = sammlung[index];
     // zuerst Einfügestelle suchen:
     int einfuegestelle = suchen(sammlung, elementZumEinfuegen, index);
     for (int j = index; j > einfuegestelle; j--) // nach oben schieben:
      sammlung[j] = sammlung[j-1];
     sammlung[einfuegestelle] = elementZumEinfuegen; } }

Aufgabe 5.4: Führen Sie die Prozedur shellSort aus, nachdem Sie sie durch Ausgaben über System.out.println ergänzt haben. Sie können damit ihre Arbeitsweise verstehen. Führen Sie den Algorithmus mit 25 Zahlen auf Papier durch und vergleichen Sie Ihr Ergebnis mit der Ausgabe.

Lösung:

Shell sort: 
kowdvjpaeiqhclyfmrubsgxnt
Schrittweite = 7

aowdvjpkeiqhclyfmrubsgxnt
aewdvjpkoiqhclyfmrubsgxnt
aeidvjpkowqhclyfmrubsgxnt
aeidvjpkowqhclyfmrubsgxnt
aeidhjpkowqvclyfmrubsgxnt
aeidhcpkowqvjlyfmrubsgxnt
aeidhclkowqvjpyfmrubsgxnt
aeidhclkowqvjpyfmrubsgxnt
aeidhclkfwqvjpyomrubsgxnt
aeidhclkfmqvjpyowrubsgxnt
aeidhclkfmqvjpyowrubsgxnt
aeidhclkfmqujpyowrvbsgxnt
aeidhblkfmqucpyowrvjsgxnt
aeidhblkfmqucpyowrvjsgxnt
aeidhblgfmqucpkowrvjsyxnt
aeidhblgfmqucpkowrvjsyxnt
aeidhblgfmqucpkonrvjsyxwt
aeidhblgfmqucpkonrvjsyxwt

Schrittweite = 3
aeidhblgfmqucpkonrvjsyxwt
aeidhblgfmqucpkonrvjsyxwt
aebdhilgfmqucpkonrvjsyxwt
aebdhilgfmqucpkonrvjsyxwt
aebdgilhfmqucpkonrvjsyxwt
aebdgflhimqucpkonrvjsyxwt
aebdgflhimqucpkonrvjsyxwt
aebdgflhimqucpkonrvjsyxwt
aebdgflhimqucpkonrvjsyxwt
aebcgfdhilqumpkonrvjsyxwt
aebcgfdhilpumqkonrvjsyxwt
aebcgfdhilpkmquonrvjsyxwt
aebcgfdhilpkmquonrvjsyxwt
aebcgfdhilnkmpuoqrvjsyxwt
aebcgfdhilnkmproquvjsyxwt
aebcgfdhilnkmproquvjsyxwt
aebcgfdhiljkmnropuvqsyxwt
aebcgfdhiljkmnropsvquyxwt
aebcgfdhiljkmnropsvquyxwt
aebcgfdhiljkmnropsvquyxwt
aebcgfdhiljkmnropsvquyxwt
aebcgfdhiljkmnropstquvxwy

Schrittweite = 1
aebcgfdhiljkmnropstquvxwy
abecgfdhiljkmnropstquvxwy
abcegfdhiljkmnropstquvxwy
abcegfdhiljkmnropstquvxwy
abcefgdhiljkmnropstquvxwy
abcdefghiljkmnropstquvxwy
abcdefghiljkmnropstquvxwy
abcdefghiljkmnropstquvxwy
abcdefghiljkmnropstquvxwy
abcdefghijlkmnropstquvxwy
abcdefghijklmnropstquvxwy
abcdefghijklmnropstquvxwy
abcdefghijklmnropstquvxwy
abcdefghijklmnropstquvxwy
abcdefghijklmnorpstquvxwy
abcdefghijklmnoprstquvxwy
abcdefghijklmnoprstquvxwy
abcdefghijklmnoprstquvxwy
abcdefghijklmnopqrstuvxwy
abcdefghijklmnopqrstuvxwy
abcdefghijklmnopqrstuvxwy
abcdefghijklmnopqrstuvxwy
abcdefghijklmnopqrstuvwxy
abcdefghijklmnopqrstuvwxy
abcdefghijklmnopqrstuvwxy

Aufgabe 5.5: Geben Sie eine Reihung der Länge 8 an, welche „besonders günstige Daten“ für quickSort enthält. Welchen Zeitbedarf hat quickSort in einem solchen günstigsten Fall?

Lösung: Günstige Fälle sind diejenigen, wo das mittlere Element den mittleren Wert enthält. Besonders günstige Daten:

a b c d e f g h

Zeitbedarf: 3 Schritte.

Aufgabe 5.6: Geben Sie eine Reihung der Länge 8 an, welche „besonders ungünstige Daten“ für quickSort enthält. Welchen Zeitbedarf hat quickSort in einem solchen ungünstigsten Fall?

Lösung: Ungünstige Daten sind diejenigen, wo sich der mittlere Wert am Rand befindet. Besonders ungünstige Daten:

d b a c g h f e

Zeitbedarf: 8 Schritte.

Aufgabe 5.7: Wie groß muss der Stapel für die Ausführung von quickSort im günstigsten bzw. im ungünstigsten Fall bzw. durchschnittlich sein? Geben Sie die Größe des Stapels in QUICK-Speichereinheiten an.

Lösung: Im günstigsten Fall n log₂ n QUICK-Speichereinheiten, im ungünstigsten Fall n QUICK-Speichereinheiten.

Aufgabe 5.8: Warum ist die folgende Reihung keine Halde?

Lösung: K auf Index 2 ist größer als J auf Index 3

Aufgabe 5.9: Geben Sie eine Halde mit sieben Komponenten an, die die Schlüssel A, B, C, D, E, F und G haben.

Lösung:

Aufgabe 5.10: Wenden Sie diesen Algorithmus auf die folgenden Reihungen an:

Lösung:

Aufgabe 5.11: Beantworten Sie folgende Fragen: Welche Fälle sind für die Prozedur senken besonders günstig? Welche sind besonders ungünstig? Welchen Zeitbedarf hat die Prozedur senken im günstigsten und im ungünstigsten Fall? Welchen Zeitbedarf hat der oben beschriebene Algorithmus, der eine Reihung in eine Halde umwandelt („1. Schritt“), im ungünstigsten Fall? Welchen Zeitbedarf hat der oben beschriebene Algorithmus, der eine Halde in eine sortierte Reihung umwandelt („2. Schritt“), im ungünstigsten Fall? Welchen Zeitbedarf hat die Prozedur heapSort im ungünstigsten Fall?

Lösung: Besonders günstig ist der Fall, wenn reihung eine Halde ist – dann muss senken nichts tun. Besonders ungünstig ist der Fall, wenn an der Spitze der „fast-Halde“ ein kleineres Element steht, als die Hälfte der Elemente (z.B. das kleinste). Dann muss senken es in log₂ n Schritten in die 2. Hälfte von reihung transportieren.

Aufgabe 5.12: Ergänzen Sie das obige Programm durch Ausgaben (System.out.println), damit Sie seine Arbeitsweise verstehen können. Führen Sie die Algorithmen mit 20 Zahlen auf Papier durch und vergleichen Sie Ihre Ergebnisse mit der Ausgabe.

Lösung:

Heap sort: 
kowdvjpaeiqhclyfmrubsgxnt

Halde aufbauen:
kowdvjpaeiqtclyfmrubsgxnh
kowdvjpaeixtclyfmrubsgqnh
kowdvjpaesxtclyfmrubigqnh
kowdvjpausxtclyfmrebigqnh
kowdvjpmusxtclyfarebigqnh
kowdvjymusxtclpfarebigqnh
kowdvtymusxnclpfarebigqjh
kowdxtymusvnclpfarebigqjh
kowuxtymrsvnclpfadebigqjh
koyuxtwmrsvnclpfadebigqjh
kxyuvtwmrsqnclpfadebigojh
yxwuvtpmrsqnclkfadebigojh

Halde abbauen:
xvwustpmriqnclkfadebhgojy
wvtusnpmriqjclkfadebhgoxy
vutrsnpmoiqjclkfadebhgwxy
ustrqnpmoigjclkfadebhvwxy
tsprqnlmoigjchkfadebuvwxy
srpoqnlmeigjchkfadbtuvwxy
rqpoinlmebgjchkfadstuvwxy
qopminlfebgjchkdarstuvwxy
ponmijlfebgachkdqrstuvwxy
omnfijldebgachkpqrstuvwxy
nmlfijkdebgachopqrstuvwxy
milfhjkdebgacnopqrstuvwxy
likfhjcdebgamnopqrstuvwxy
kijfhacdebglmnopqrstuvwxy
jigfhacdebklmnopqrstuvwxy
ihgfbacdejklmnopqrstuvwxy
hfgebacdijklmnopqrstuvwxy
gfdebachijklmnopqrstuvwxy
fedcbaghijklmnopqrstuvwxy
ecdabfghijklmnopqrstuvwxy
dcbaefghijklmnopqrstuvwxy
cabdefghijklmnopqrstuvwxy
bacdefghijklmnopqrstuvwxy
abcdefghijklmnopqrstuvwxy
abcdefghijklmnopqrstuvwxy

Aufgabe 5.13: Programmieren Sie dieses Verfahren. Entwickeln Sie die Klasse Sortierkanal mit folgender Spezifikation:

interface Element {
   boolean less(final Element element);
}

abstract class Sortierkanal {
   public Sortierkanal(int groesse) { ... }
   public void sortierkanal() { ... }
   // ruft lesen öfter auf, um das nächste Element einzulesen
   // ruft schreiben öfter auf, um das kleinste gelesene Element auszugeben
   // ruft sequenzEnde, wenn das auszugebende Element kleiner als das letzte
   abstract Element lesen() throws Ende;
   abstract void schreiben(final Element element);
   abstract void sequenzEnde();
}

Lösung:

abstract class ASortierkanal {
   abstract Element lesen() throws EndeException;
   abstract void schreiben(final Element element);
   abstract void sequenzEnde();

   private Element[] halde;
   public ASortierkanal(int groesse) {
     halde = new Element[groesse+1]; // Platz 0 bleibt unbenutzt
   }

   private class Halde { // operiert an der Reihung halde
     private int anfang, ende; // aktuelle Grenzen der Halde innerhalb der Reihung halde
     Halde() {
      anfang = halde.length;
      ende = anfang - 1; }
     boolean istLeer() {
      return anfang > ende; }
     boolean istVoll() {
      return anfang == 1; }
     Element spitze() {
      return halde[anfang]; }
     void senken() {
      // halde[anfang..ende] wird durch das senken des Elements halde[anfang-1] 
      // zur halde[anfang-1..ende] erweitert.
      int index = anfang - 1; // linke Grenze der neuen Halde
      int nachfolger = anfang; 
      final Element zuSenken = halde[index]; // neues Element
      while(true) {
      if (nachfolger > ende) break; // weil nachfolger nicht existiert
        if (nachfolger < ende && halde[nachfolger+1].less(halde[nachfolger])) 
          // größeren nachfolger oder nachfolger+1 auswählen
          nachfolger ++;
      if (zuSenken.less(halde[nachfolger])) break; // Platz gefunden
        halde[index] = halde[nachfolger]; // hochrücken
        index = nachfolger; // runtergehen
        nachfolger = 2 * index - anfang + 1; // linker nachfolger, wenn existiert
      }
      halde[index] = zuSenken; // Element einfügen
      anfang --; // Halde wurde nach unten erweitert
     }
     void fuellen(Element zumEinfuegen) {
      // fügt Element in die halde[anfang .. ende] ein,
      // indem sie entweder zu halde[anfang - 1 .. ende] verlängert 
      // oder das Spitzenelement ausgegeben wird
      if (istVoll()) {
        schreiben(spitze());
        zuletztGeschrieben = spitze();
        anfang++; // Platz machen
      }
      halde[anfang-1] = zumEinfuegen; // neues Element eintragen
      senken();
     }
     void entleeren() {
      // gibt das Element halde[anfang] aus und erzeugt die halde[anfang .. ende-1], 
      // indem halde[ende] gesenkt wird
      schreiben(spitze());
      zuletztGeschrieben = spitze();
      halde[anfang] = halde[ende] ; // hinteres Element
      anfang ++; // neues Element noch nicht gesenkt
      ende --; // Halde hinten verkürzen
      senken(); // in der verkürzten Halde
     }
   }

   private Element zuletztGeschrieben;
   void sortierkanal() {
     Element aktuelles; // das aktuelle Element
     boolean erstes = true; // noch kein Element wurde geschrieben
     final int grenze = halde.length-1;
     Halde aktiv = new Halde(), ersatz = new Halde(); // zwei leere Halden
     try {
      while (true) { // Aussprung bei EndeException von lesen()
        aktuelles = lesen();
        if (! aktiv.istVoll()) // Halde noch nicht voll, aufbauen:
          aktiv.fuellen(aktuelles);
        else if (erstes || ! aktuelles.less(zuletztGeschrieben)) { 
          // aktuelles gehört dieser Sequenz
          erstes = false;
          if (aktuelles.less(aktiv.spitze()) && !aktuelles.less(zuletztGeschrieben)) {
           // sofort ausgeben:
           schreiben(aktuelles);
           zuletztGeschrieben = aktuelles;
          } else { // wurde schon kleineres ausgegeben
           aktiv.fuellen(aktuelles); // fuellen ruft schreiben auf, wenn Halde voll
          } // nicht sofort ausgeben
        } else { // aktuelles gehört der nächsten Sequenz, in die Ersatzhalde:
          if (!aktiv.istLeer()) {
           aktiv.entleeren(); // in der aktiven Halde wird Platz gemacht:
                 // entleeren ruft schreiben auf und verkürzt die aktive Halde
           ersatz.fuellen(aktuelles);
          } else { // aktiv.istLeer()
           sequenzEnde(); // aktuelle Sequenz ist zu Ende
           aktiv = ersatz;
           ersatz = new Halde();
           aktiv.fuellen(aktuelles); // fuellen ruft schreiben auf, wenn Halde voll
          }
        }
      } // Leseschleife
     } catch (EndeException e) { } // einlesen fertig
     // alle Eingabedaten wurden eingelesen; zuerst aktive Halde abbauen:
     if (aktiv.spitze().less(zuletztGeschrieben))
      sequenzEnde();
     while (! aktiv.istLeer())
      aktiv.entleeren();
     // Ersatzhalde abbauen:
     sequenzEnde();
     while (! ersatz.istLeer())
      ersatz.entleeren();
     sequenzEnde();
   }
}

Aufgabe 5.14: Entwickeln Sie eine Tabelle für k = 4, ähnlich der Tabelle 5.14. Zeichnen Sie das Verfahren, wie 100 Sequenzen nach dem Fibonacci-Algorithmus gemischt werden.

Lösung: fehlt noch