2. Suchen und Sortieren

Die Operationen Suchen und Sortieren stellen zwei der zentralen Operationen der Informatik dar. Sie werden hier exemplarisch auf der Datenstruktur Feld besprochen, spielen aber auch bei den Datenstrukturen Liste und Suchbaum eine zentrale Rolle.

Zur weiteren Vereinfachung werden Felder über dem primitiven Datentyp int betrachtet. Felder über Objekten werden im Rahmen der linearen Datenstrukturen besprochen.

Suchen

Lineare Suche

Bei der linearen Suche wird das Feld von vorn nach hinten sequentiell solange durchsucht, bis das gewünschte Element gefunden wird (erfolgreiche Suche) oder das Feld erfolglos vollständig abgesucht wurde (erfolglose Suche). Es ist leicht einzusehen, dass die lineare Suche lineare Laufzeit besitzt.

Als Konvention gibt die Methode hier nicht nur die Erfolgsmeldung aus (true/false), sondern die Position des gefunden Elements bzw. -1 im Falle der erfolglosen Suche.

public int starteLineareSuche(int[] array, int key) { 

    for (int i=0; i<array.length; i++) {

        if (array[i]==key) {
            return i;
        }

    }

    return -1;
}

Binäre Suche

Die binäre Suche setzt ein bereits sortiertes Feld voraus (vgl. nächster Abschnitt Sortieren). Diese Sortierung wird durch die Idee der Intervallhalbierung ausgenutzt. In jedem Durchlauf wird die mittlere Position des verbleibenden Suchraums bestimmt. Ist das gesuchte Element an dieser Stelle vorhanden, so wird die Suche erfolgreich beendet. Ist das gesuchte Element kleiner, so kann der Suchraum auf alle Feldelemente links von der mittleren Position eingeschränkt werden. Ist das Element größer, so kann der Suchraum entsprechend auf alle Feldelemente rechts von der mittleren Position eingeschränkt werden. Sollten sich die Suchraumgrenzen gegenseitig überholen (l>r), so wird die Suche erfolglos abgebrochen.

Durch die Intervallhalbierung ist eine logarithmische Laufzeit bedingt, die viel besser als eine lineare Laufzeit einzustufen ist. Allerdings darf nicht vergessen werden, dass der zusätzliche Aufwand der Sortierung ebenfalls Laufzeit kostet.

public int starteBinaereSuche(int[] array, int key) {

    // Lege die Bereichsgrenzen fest
    int n = array.length;
    int m;

    int l = 0;
    int r = n-1;

    while (l<=r) {

        // Bestimme Mitte 
        m = (l+r) / 2;

        // Unterscheide drei Fälle

        // 1. Fall: GEFUNDEN
        if (array[m] == key) { 
            return m;
        }

        // 2. Fall: Suche LINKS weiter
        else if (key < array[m]) { 
            r = m-1;
        }

        // 3. Fall: Suche RECHTS weiter
        else { 
            l = m+1;
        }

    }

    return -1;

}

Sortieren

BubbleSort

Das vermutlich bekannteste Sortierverfahren ist BubbleSort. Hier wird in einem Felddurchlauf für je zwei Nachbarelemente geschaut, ob sie sich in der richtigen Reihenfolge befinden. Wenn nicht, so werden sie getauscht (paarweises Tauschen). Auf diese Weise rutscht das größte Element im ersten Durchlauf an die letzte Position, das zweitgrößte Element im zweiten Durchlauf an die vorletzte Position usw. Es ergibt sich insgesamt eine quadratische Laufzeit.

public void doBubbleSort(int[] feld) {

    int hilfe;

    for (int i=feld.length-1; i>=1; i--) {

      for (int j=0; j<=i-1; j++) {

        if (feld[j] > feld[j+1]) {
          hilfe = feld[j];
          feld[j] = feld[j+1];
          feld[j+1] = hilfe;
        }

      }

    }

}

Straight Selection

Beim Sortieren durch Auswahl bzw. Straight Selection wird im ersten Durchlauf das kleinste Element an die 0-te Stelle des Felds, im zweiten Durchlauf das zweitkleinste Element an die 1-te Stelle des Felds usw. gebracht. Bei der Suche nach dem verbleibenden kleinsten Element wird das Restfeld von vorn nach hinten durchlaufen. Es ergibt sich wieder eine quadratische Laufzeit.

public void doStraightSelection(int[] feld) {

    int hilfe;

    for (int i=0; i<feld.length; i++) {

      for (int j=i+1; j<feld.length; j++) {

        if (feld[j]<feld[i]) {
          hilfe = feld[j];
          feld[j] = feld[i];
          feld[i] = hilfe;
        }

      }
    }

}

Straight Insertion

Beim Sortieren durch Einfügen (Straight Insertion) wird nach und nach ein immer größer werdendes sortiertes Teilfeld aufgebaut. Im ersten Schritt ist das Teilfeld, das nur aus dem ersten Element besteht, bereits sortiert. Nun wird das zweite Element mit in das sortierte Teilfeld aufgenommen, d.h. es wird an der passenden Einfügestelle eingefügt. Diese Idee wiederholt sich so lange, bis das gesamte Feld sortiert ist. Auch dieses Verfahren weist wieder quadratische Laufzeit auf.

public void doStraightInsertion(int[] feld) {

    int hilfe;

    for (int i=1; i<feld.length; i++) {

      int j=0;

      while ((j<i) && (feld[j]<feld[i])) {
        j++;
      }

      hilfe = feld[i];

      for (int k=i; k>=j+1; k--) {
        feld[k] = feld[k-1];
      }

      feld[j] = hilfe;

    }

}

Schnelle Sortierverfahren

Es gibt weitere Sortierverfahren, die mit n log n eine Laufzeit aufweisen, die der quadratischen überlegen ist. Stellvertretend sei hier QuickSort genannt, das als rekursives Verfahren im Abschnitt Rekursive Algorithmen vorgestellt wird.