Sortieraufwand

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