Arbeitsblätter und Lösungen Hr. Kimmig
package _quicksort;
import java.util.Random;
public class Quicksort {
public static void main(String[] args) {
Random rand = new Random();
// Erzeuge Array für 20 Zahlen
int[] a = new int[100000];
// generiere Zufallszahlen und speichere diese im Array
for( int i = 0 ; i < a.length ; i++ ) {
a[i] = rand.nextInt(50);
}
// Array ausgeben
for( int i = 0 ; i < a.length ; i++ ) {
// System.out.print(a[i] + ", ");
}
System.out.println();
long start = System.currentTimeMillis();
a = quicksort(a);
long end = System.currentTimeMillis();
System.out.println(end-start);
for( int i = 0 ; i < a.length ; i++ ) {
// System.out.print(a[i] + ", ");
}
System.out.println();
}
public static int[] quicksort(int[] arr) {
if(arr.length<=1) return arr; // Abbruchbedingung
int pivot = arr[arr.length-1]; // Wähle Pivot-Element
// Elemente zählen, die kleiner als das Pivot-Element sind
int größelinks = 0;
for( int i=0 ; i<arr.length-1 ; i++ ) {
if( arr[i] < pivot ) {
größelinks++;
}
}
// Anzahl der Elemente, die größer als das Pivot-Element sind
int größerechts = arr.length - größelinks - 1;
// Erzeuge Arrays mit passender Größe
int[] links = new int[größelinks];
int[] rechts = new int[größerechts];
// li: nächste freie Stelle im linken Array
int li = 0;
// ri: nächste freie Stelle im rechten Array
int ri = 0;
// sortiere die Elemente nach links und rechts
for(int i=0 ; i<arr.length-1 ; i++) {
if(arr[i]<pivot) {
links[li] = arr[i];
li++;
}
else {
rechts[ri] = arr[i];
ri++;
}
}
/*// Überprüfung: Ausgabe der Teilarrays und des Pivot-Elements
System.out.println("Pivot: "+pivot);
System.out.print("links: ");
for(int i=0 ; i<links.length ; i++) {
System.out.print(links[i] + ", ");
}
System.out.println();
System.out.print("rechts: ");
for(int i=0 ; i<rechts.length ; i++) {
System.out.print(rechts[i] + ", ");
}
System.out.println();*/
// Schritt 3: Rekursion
links = quicksort(links);
rechts = quicksort(rechts);
// Schritt 4: Zusammensetzen
// Kopiere die Elemente des linken Arrays in das Ausgangsarray ab Stelle 0
System.arraycopy(links, 0, arr, 0, links.length);
// Kopiere das Pivot-Element an die Stelle links.length
arr[ links.length ] = pivot;
// Kopiere das rechte Array, beginne ab Stelle links.length+1
System.arraycopy(rechts, 0, arr, links.length+1, rechts.length);
return arr;
}
}