QuickSort.java

import java.io.*;

public class QuickSort {
  // Beispielprogramm für Quicksort-Algorithmus
  
  public static void main(String[] args) throws IOException {
    // erzeugt ein Array von Zufallszahlen und gibt es sortiert aus
    
    BufferedReader in = new BufferedReader(
    new InputStreamReader(System.in));
    
    // Größe des Arrays erfragen
    String s;    // String für eingegebene Zeile
    System.out.println("Anzahl der zu sortierenden Werte eingeben:");
    s = in.readLine();
    int anzahl = Integer.parseInt(s);
    // abfragen, ob Liste ausgegeben werden soll
    System.out.println("Soll die sortierte Liste ausgegeben werden (j/n):");
    s = in.readLine();
    boolean mitAusgabe = false;
    if (s.compareTo("j") == 0) {
      mitAusgabe = true;
    }
    
    // erzeuge die Liste
    double[] liste = new double[anzahl];
    
    // fülle die Liste mit Zufallszahlen
    for (int i = 0; i < anzahl; i++) {
      liste[i] = Math.random();
    }
    
    // sortiere die Liste und miss die benötigte Zeit
    long timeBefore = System.currentTimeMillis();
    sort(liste);
    long timeAfter = System.currentTimeMillis();
    double timeSpent = (timeAfter - timeBefore)/1000.0;  // in s
    System.out.println("Zeit zum Sortieren: " + timeSpent + "s");
    
    // gib die Liste aus, falls gewünscht
    if (mitAusgabe) {
      for (int i = 0; i < anzahl; i++) {
        System.out.println(liste[i]);
      }
    }
  }
  
  
  static void sort(double[] liste) {
    quicksort(liste, 0, liste.length - 1);
  }
  
  
  static void quicksort(double[] a, int oben, int unten) {
    int high = oben;
    int low = unten;
    double x = a[(high+low)/2];   // "mittleres" Element
    
    do {
      while (a[high] < x) {  // suche großes Element bei den Kleinen
        high++;
      }
      while (a[low] > x) {  // suche kleines Element bei den Großen
        low--;
      }
      if (high <= low) {
        vertausche(a, high, low);
        high++;
        low--;
      }
    } while (high <= low);
    
    if (oben < low) {  // Abbruchbedingung
      quicksort(a, oben, low);
    }
    
    if (high < unten) {  // Abbruchbedingung
      quicksort(a, high, unten);
    }
  }
  
  // vertausche a[i] und a[j]
  static void vertausche(double[] a, int i, int j) {
    double temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
}