118 lines
3.1 KiB
Java
118 lines
3.1 KiB
Java
|
|
/**
|
|
* Beschreiben Sie hier die Klasse QuickSort.
|
|
*
|
|
* @author (Ihr Name)
|
|
* @version (eine Versionsnummer oder ein Datum)
|
|
*/
|
|
import java.util.Random;
|
|
public class QuickSort
|
|
{
|
|
static Random r = new Random();
|
|
static int[] a = new int[10000000];
|
|
// gibt eine zufällige Zahl von 1-50 zurück
|
|
public static int Zufallszahl(){
|
|
return r.nextInt(100000 );
|
|
}
|
|
public static void main(){
|
|
// array mit 20 zufallszahlen von 1-50 belegen
|
|
for (int i = 0; i < a.length; i++){
|
|
a[i] = Zufallszahl();
|
|
}
|
|
/* ausgeben des arrays "a"
|
|
for (int i = 0; i < a.length; i++){
|
|
System.out.print(a[i]);
|
|
System.out.print(",");
|
|
}
|
|
*/
|
|
// absatz
|
|
System.out.println();
|
|
long start = System.currentTimeMillis();
|
|
qi(a, 0, a.length -1);
|
|
long ende = System.currentTimeMillis();
|
|
/* ausgeben des arrays "a"
|
|
for (int i = 0; i < a.length; i++){
|
|
System.out.print(a[i]);
|
|
System.out.print(",");
|
|
}
|
|
*/ System.out.println();
|
|
System.out.println(ende - start);
|
|
}
|
|
|
|
public static int[] q(int[] a){
|
|
// 0. Abbrruchbedingung
|
|
if (a.length < 2) return a;
|
|
// 1. Pivot
|
|
int pivot = a[a.length -1];
|
|
// 2. Elemente kleiner als Pivot zählen
|
|
int kleiner = 0;
|
|
for (int i = 0; i < a.length - 1; i++){
|
|
if (a[i] < pivot ) kleiner++;
|
|
}
|
|
// 3. Arrays erstellen
|
|
int[] links = new int[kleiner];
|
|
int[] rechts = new int[a.length - kleiner -1];
|
|
// 4. Arrays befüllen
|
|
int r = 0;
|
|
int l = 0;
|
|
for (int i = 0; i< a.length - 1; i ++){
|
|
if (a[i] < pivot){
|
|
links[l] = a[i];
|
|
l++;
|
|
}
|
|
else{
|
|
rechts[r] = a[i];
|
|
r++;
|
|
}
|
|
}
|
|
// 5. Arrays rekursiv sortieren
|
|
links = q(links);
|
|
rechts = q(rechts);
|
|
|
|
// 6. Zusammensetzen
|
|
for (int i = 0 ; i < links.length; i ++){
|
|
a [i] = links[i];
|
|
}
|
|
a[links.length] = pivot;
|
|
for (int i = 0; i < rechts.length; i++){
|
|
a[links.length + i + 1]= rechts[i];
|
|
}
|
|
return a;
|
|
}
|
|
public static int[] qi(int [] a, int l , int r){
|
|
//Abrruchbedingung
|
|
if (r-l < 2) return a;
|
|
// pivot
|
|
int pivot = a[r];
|
|
int i = l;
|
|
int j = r -1;
|
|
// vertauschen
|
|
while (i < j){
|
|
if (a[i] < pivot) i++;
|
|
if (a[j] >= pivot) j--;
|
|
|
|
if (a[i] >= pivot && a[j] < pivot){
|
|
int tmp = a[i];
|
|
a[i] = a[j];
|
|
a[j] = tmp;
|
|
}
|
|
}
|
|
// pivot an richtige Stelle
|
|
int stelle = 0;
|
|
if (a[i] > pivot) {
|
|
a[r] = a[i];
|
|
a[i] = pivot;
|
|
stelle = i;
|
|
}
|
|
else {
|
|
a[r] = a[i +1];
|
|
a[i+1] = pivot;
|
|
stelle = i+1;
|
|
}
|
|
// rekursiver Aufruf
|
|
qi(a, l, stelle - 1);
|
|
qi(a, stelle + 1 , r);
|
|
return a;
|
|
}
|
|
}
|