Rekursive Algorithmen

An dieser Stelle werden exemplarisch zwei bekannte rekursive Algorithmen vorgestellt.

Binäre Suche

Als erstes Beispiel wird die binäre Suche auf einem Feld vorgestellt. Gegenüber der iterativen Lösung wird der Suchraum hier durch den rekursiven Aufruf verkleinert. Zu Beginn wird der Suchvorgang auf dem kompletten Feld in Gang gebracht. Je nach Fall verengt sich der Suchraum in jeder Rekursionsebene, bis entweder das gewünschte Element gefunden wurde oder der Suchraum leer ist (Fall l>r).

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

    int n = array.length;

    return sucheBinaer(array, key, 0, n-1);    
}

/* Fuehrt die eigentliche binaere Suche durch. */
private int sucheBinaer(int[] array, int key, int l, int r) {

    // Abbruchbedingung fuer erfolglose Suche: l>r
    if (l>r) { return -1; }

    // Bestimme die Mitte des Feldabschnitts
    int m = (l+r) / 2;

    // Unterscheide die drei F?lle

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

    // 2. Fall: Suche LINKS weiter
    else if (key < array[m]) { 
        return sucheBinaer(array, key, l, m-1);
    }

    // 3. Fall: Suche RECHTS weiter
    else { 
        return sucheBinaer(array, key, m+1, r);
    }

}

QuickSort

Das Sortierverfahren QuickSort basiert auf einer simplen Idee, die rekursiv elegant umgesetzt werden kann: Bestimme im aktuellen Teilfeld ein vermutlich mittelgroßes Element (Pivot-Element) und ordne nun links vom Pivot alle kleineren und rechts vom Pivot alle größeren Elemente an. Sortiere den linken und rechten Bereich anschließend durch zwei Rekursionsaufrufe.

public void doQuickSort(int[] feld) {

      quickSort(feld,0,feld.length-1);

}

private void quickSort(int[] feld, int l, int r) {  

      if (l>=r) { return; }

      int i, j, m;
      int pivot, hilf;

      // Bestimme Pivotelement
      i = l;
      j = r;
      m = (l+r)/2;
      pivot = feld[m];

      // Teile in zwei Teilfelder
      while (i<=j) {
          while (feld[i]<pivot) { i++; }
          while (feld[j]>pivot) { j--; }
          if (i<=j) { // Tausche Feldinhalte
              hilf = feld[i];
              feld[i] = feld[j];
              feld[j] = hilf;
              i++;
              j--;
          }
      }

      quickSort(feld,i,r);
      quickSort(feld,l,j);

}

results matching ""

    No results matching ""