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;
}
}