28.5 Sortieraufwand und O-Kalkül
28.5.1 Sortieraufwand experimentell

One plus one is two.
Two plus two is four
Four plus four is eight.
Eight plus eight is more than ten.

Kinderreim

 


 
Ein einfaches Programm (siehe Download) testet den zeitlichen Aufwand, den die einzelnen Sortieralgoritmen benötigen:
Download:

Sortieren Vergleich.java
Sortieren.java
StoppUhr.java

public class SortierenVergleich {

   public static void main(String[] args){
      StoppUhr uhr = new StoppUhr();
      int[] liste1;
      System.out.print("Laenge der Liste: ");
      int anzahl = Console.in.readInt();

      liste1 = Sortieren.listeAnlegen(anzahl);
      int[] liste2 = (int[]) liste1.clone();
      int[] liste3 = (int[]) liste1.clone();
      int[] liste4 = (int[]) liste1.clone();

      uhr.starten();
      Sortieren.bubbleSort(liste1);
      uhr.stoppen();
      System.out.println("\n\nSortierzeit BubleSort: "+uhr);

      uhr.starten();
      Sortieren.einfuegen(liste2);
      uhr.stoppen();
      System.out.println("\n\nSortierzeit Einfuegen: "+uhr);
      
      uhr.starten();
      Sortieren.heapSort(liste3);
      uhr.stoppen();
      System.out.println("\n\nSortierzeit HeapSort: "+uhr);

      uhr.starten();
      Sortieren.quickSort(liste4);
      uhr.stoppen();
      System.out.println("\n\nSortierzeit QuickSort: "+uhr);
   }
}
  Um sicherzustellen, dass immer die gleiche Liste von Zufallszahlen sortiert wird, erzeugen wir einmal eine Liste liste1 und durch Klonen erzeugen wir die Instanzen liste2, liste3 und liste4.
  Deutliche Unterschiede in der benötigten Sortierzeit zeigen sich mit steigender Anzahl der zu sortierenden Zahlen in den Listen. Die Stärken von Quicksort und Heapsort zeigen sich am deutlichsten bei sehr großen Listen. Um eine Statistik zu machen dient ein anderes kleines Programm:
 
Download:
SortierVergleich2. java
public class SortierenVergleich2 {

  public static void main(String[] args){
    StoppUhr uhr = new StoppUhr();
    int stat = 10;

    for(int i = 5000; i < 100000; i += 5000)  {
      long totalZeitBubble = 0;
      long totalZeitEinfuegen = 0;
      long totalZeitHeap = 0;
      long totalZeitQuick = 0;

      for (int j = 0; j < stat; j++){

        int[] liste1 = Sortieren.listeAnlegen(i);
        int[] liste2 = (int[]) liste1.clone();
        int[] liste3 = (int[]) liste1.clone();
        int[] liste4 = (int[]) liste1.clone();

        uhr.starten();
        Sortieren.bubbleSort(liste1);
        uhr.stoppen();
        totalZeitBubble += uhr.getLaufzeit();

        uhr.starten();
        Sortieren.einfuegen(liste2);
        uhr.stoppen();
        totalZeitEinfuegen += uhr.getLaufzeit();

        uhr.starten();
        Sortieren.heapSort(liste3);
        uhr.stoppen();
        totalZeitHeap += uhr.getLaufzeit();

        uhr.starten();
        Sortieren.quickSort(liste4);
        uhr.stoppen();
        totalZeitQuick += uhr.getLaufzeit();
      }
      System.out.println("n = "+i);
      System.out.println("--------------");
      System.out.println("BubbleSort : "
                          +totalZeitBubble/1000.0/stat);
      System.out.println("Einfuegen  : "
                          +totalZeitEinfuegen/1000.0/stat);
      System.out.println("HeapSort   : "
                          +totalZeitHeap/1000.0/stat);
      System.out.println("QuickSort  : "
                          +totalZeitQuick/1000.0/stat);
      System.out.println("\n");
    }
  }
}
  Um statistische Streuungen zu minimieren, werden alle Werte 10 mal erfasst und ihr Durchschnittswert ausgegeben. Achtung: Die Laufzeit des Programms ist selbst bei schnellen Rechnern sehr groß: Für eine Pentium III 450 MHz und 256 MB Hauptspeicher ergaben sich folgende Werte:
 
 
n = 5000
--------------
BubbleSort : 0.4888
Einfuegen  : 0.192
HeapSort   : 0.0080
QuickSort  : 0.0050
MergeSort  : 0.0061
 
n = 10000
--------------
BubbleSort : 1.9399
Einfuegen  : 0.8261
HeapSort   : 0.0210
QuickSort  : 0.0080
MergeSort  : 0.012
 
n = 15000
--------------
BubbleSort : 4.2652
Einfuegen  : 1.9267
HeapSort   : 0.03
QuickSort  : 0.01
MergeSort  : 0.0211
 
n = 20000
--------------
BubbleSort : 6.6786
Einfuegen  : 3.1735
HeapSort   : 0.0402
QuickSort  : 0.0140
MergeSort  : 0.019
 
n = 25000
--------------
BubbleSort : 10.2279
Einfuegen  : 4.9351
HeapSort   : 0.05
QuickSort  : 0.02
MergeSort  : 0.0701
 
n = 30000
--------------
BubbleSort : 14.8525
Einfuegen  : 7.2453
HeapSort   : 0.064
QuickSort  : 0.0272
MergeSort  : 0.031
 
n = 35000
--------------
BubbleSort : 19.8414
Einfuegen  : 9.7371
HeapSort   : 0.0751
QuickSort  : 0.0301
MergeSort  : 0.0361
 
n = 40000
--------------
BubbleSort : 25.9265
Einfuegen  : 12.9304
HeapSort   : 0.093
QuickSort  : 0.0361
MergeSort  : 0.0441
 
n = 45000
--------------
BubbleSort : 32.4793
Einfuegen  : 16.4817
HeapSort   : 0.1024
QuickSort  : 0.039
MergeSort  : 0.0492
 
n = 50000
--------------
BubbleSort : 41.811
Einfuegen  : 21.0934
HeapSort   : 0.1122
QuickSort  : 0.049
MergeSort  : 0.0521
 
n = 55000
--------------
BubbleSort : 49.2909
Einfuegen  : 24.8048
HeapSort   : 0.1231
QuickSort  : 0.0482
MergeSort  : 0.064
 
n = 60000
--------------
BubbleSort : 57.8501
Einfuegen  : 29.2932
HeapSort   : 0.1361
QuickSort  : 0.0520
MergeSort  : 0.0692
 
n = 65000
--------------
BubbleSort : 68.0280
Einfuegen  : 34.4675
HeapSort   : 0.1564
QuickSort  : 0.061
MergeSort  : 0.073
 
 
Grafische Darstellung (Intel 540 MHz ; Einzelwertmessungen mit MIttelwertbildung):

 

   
zu 28.5.2 Definition des O-Kalküls
zur Startseite www.pohlig.de  (C) MPohlig 2006