28.5.3 Abschätzungen für die Sortieralgorithmen
 
BubbleSort Um den Aufwand beim BubbleSort abschätzen zu können, schauen wir uns noch einmal die Implementierung der Methode an. Der Erste Eintrag in der Liste wird mit alle anderen Einträgen in der Liste verglichen, somit wir haben n-1 Vergleiche. Das zweite Glied mit dem Rest also n-2 Vergleiche, usw. Wir haben also insgesamt

(n-1) + (n-2) + (n-3) + .. + 1 = (n-1)(n-2)/2

Vergleiche. Somit ist der Aufwand O(n2). Analog kann man begründen dass auch die Anzahl der Vertauschungen (worst case) eine Funktion O(n2) ist.

  public static void bubbleSort(int[] liste) {

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

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

        if (liste[j] < liste[i]) {

          tausche(liste, i, j);

        }

      }

    }

  }

Aufwand: O(n2)

Vergleiche: O(n2)
Vertauschungen: O(n2)
 
Einfügen 
  public static void einfuegen(int[] liste) {

    int schluessel;

    int lauf;

    for (int index = 1; index < liste.length; index++) {

      schluessel = liste[index];

      lauf = index - 1;

      while (lauf >= 0 && liste[lauf] > schluessel) {

        liste[lauf + 1] = liste[lauf];

        lauf--;

      }

      liste[lauf + 1] = schluessel;

    }

  }


Auch hier ist leicht einzusehen, dass die Anzahl der Vergleiche (worst case)

1 + 2 + 3 + ... + n-1 = (n-1)(n-2)/2 Î O(n2) ist. Ebenso sind die Anzahl der möglichen Vertauschungen (wieder worst case)  1 + 2 + 3 + ... + n-1 =
(n-1)(n-2)/2 Î O(n2), so dass insgesamt für den Aufwand gilt

Aufwand: O(n2)

Vergleiche:  O(n2)
Verschiebeoperationen:  O(n2)
 
QuickSort Der Aufwand wird bestimmt durch die rekursive Methode
  private static void quickSort(String[] liste, 

                                int untereGrenze, 

                                int obereGrenze) {

    int links = untereGrenze;

    int rechts = obereGrenze;

    String pivot = liste[((untereGrenze + obereGrenze) / 2)];

    do {

      while (liste[links].compareTo(pivot)<0) {

        links++;

      }

      while (pivot.compareTo(liste[rechts])<0) {

        rechts--;

      }

      if (links <= rechts) {

        tausche(liste, links, rechts);

        links++;

        rechts--;

      }

    } while (links <= rechts);

    if (untereGrenze < rechts) {

       quickSort(liste, untereGrenze, rechts);

    }

    if (links < obereGrenze) {

        quickSort(liste, links, obereGrenze);

    }

  }

Wir haben beim ersten Aufruf n-1 Vergleich in der do-while Schleife. Nehmen wir an, dass die Elemente so verteilt sind, dass das Aufteilen in Teillisten durch das pivot-Element immer wieder gleich große Listen erzeugt (nicht worst case), so können wir für den Aufwand A(n) sagen.      

A(n)

  = n-1 + 2*A(n/2)
   =  n-1  + 2*(n/2 -1) + 2*A(n/4) = n-1 + n-2 + A(n/8)
   = n* log2n - C Î O(n) * O(log n)
A(n)  Î O(n*log n)
  Für das Vertauschen gilt das gleiche.
   

Aufwand: O(n* log n)
 
  Vergleiche:  O(n*log n)
: Verschiebeoperationen: O(n*log n)
   
zu 28.5.4 Übungen
zur Startseite www.pohlig.de  (C) MPohlig 2006