Hallo
Ich beschäftige mich gerade mit dem QuickSort genau gesagt mit der Wahl eines geeigneten Pivot-Elements zur Steigerung der Effizienz.
Soweit ich gelernt habe, trägt die Wahl des Pivot-Elements maßgeblich zur Effizienz des Algorithmus bei. Dies wollte ich einmal überprüfen, indem ich drei verschieden Varianten, die sich in ihrer Wahl des Pivot-Elements unterscheiden, programmiert habe.
Variante 1: quickSortLinks
Immer das linke Element als Pivot nehmen
Variante 2: quickSortMitte
Immer ein Element aus der Mitte nehmen
Variante 3 quickSortRandom
Drei Werte Random aussuchen und dann das nehmen, welches vom Wert in der Mitte liegt.
Die Effizienz überprüfe ich mit einem einfachen Zähler, der Vergleiche. Alle drei Algorithmen laufen auf einem eigenen Array, welches aber von der Int-Wert Belegung identisch sind.
Zu meinem Erstaunen benötigen alle drei Algorithmen fast genau die gleiche Anzahl an vergleichen, um das Array zu sortieren.
Jetzt frage ich mich, habe ich etwas falsch gemacht?
- Zähler an der falschen stelle
- falscher QuickSort-Algorithmus? (Der Grund-Algo, stammt von dieser Seite: http://www.algolist.net/Algorithms/Sorting/Quicksort)
- wer weiß was… ;-)
Hier einmal der Code.
Ich habe die drei Algorithmen auf einem Array der Größe 10000, mit random Elemente zwischen 0 und 1000, laufen lassen. Ausgabe siehe Anhang
Im Anhang mein BlueJ-Projekt.
Ich würde gerne wissen, ob ich einen Fehler gemacht habe, oder ob das mit der Wahl des Pivot-Elements doch nicht stimmt. (kann ich mir ja eigentlich nicht vorstellen)
viele liebe Grüße,
Deggit
Ich beschäftige mich gerade mit dem QuickSort genau gesagt mit der Wahl eines geeigneten Pivot-Elements zur Steigerung der Effizienz.
Soweit ich gelernt habe, trägt die Wahl des Pivot-Elements maßgeblich zur Effizienz des Algorithmus bei. Dies wollte ich einmal überprüfen, indem ich drei verschieden Varianten, die sich in ihrer Wahl des Pivot-Elements unterscheiden, programmiert habe.
Variante 1: quickSortLinks
Immer das linke Element als Pivot nehmen
Variante 2: quickSortMitte
Immer ein Element aus der Mitte nehmen
Variante 3 quickSortRandom
Drei Werte Random aussuchen und dann das nehmen, welches vom Wert in der Mitte liegt.
Die Effizienz überprüfe ich mit einem einfachen Zähler, der Vergleiche. Alle drei Algorithmen laufen auf einem eigenen Array, welches aber von der Int-Wert Belegung identisch sind.
Zu meinem Erstaunen benötigen alle drei Algorithmen fast genau die gleiche Anzahl an vergleichen, um das Array zu sortieren.
Jetzt frage ich mich, habe ich etwas falsch gemacht?
- Zähler an der falschen stelle
- falscher QuickSort-Algorithmus? (Der Grund-Algo, stammt von dieser Seite: http://www.algolist.net/Algorithms/Sorting/Quicksort)
- wer weiß was… ;-)
Hier einmal der Code.
Java:
import java.util.Random;
/**
* Beschreiben Sie hier die Klasse Sortieren.
*
* @author (Ihr Name)
* @version (eine Versionsnummer oder ein Datum)
*/
public class QuickSortPivot
{
int n;
int vergleicheLinks=0, vergleicheMitte=0, vergleicheRandom=0;
private int[] arr1;
private int[] arr2;
private int[] arr3;
/**
* Konstruktor für Objekte der Klasse Sortieren
*
* @param pElemente Anzahl der zu sortierenden Elemente
*
*/
public QuickSortPivot(int pElemente)
{
System.out.print('\u000C'); // Konsole leeren.
arr1 = new int[pElemente];
arr2 = new int[pElemente];
arr3 = new int[pElemente];
arrayFuellen();
arrayDuplizieren();
System.out.println("Elemente des unsortierten Arrays:");
arrayAusgebenLinks(arr1);
System.out.println("");
quicksortLinks(arr1, 0, arr1.length-1);
System.out.println("Pivot-Element Links");
arrayAusgebenLinks(arr1);
System.out.println("");
//quicksortLinks(arr1, 0, arr1.length-1);
//System.out.println("Pivot-Element Links - Erneutes Sortieren auf dem bereits sortierten Array");
//arrayAusgebenLinks(arr1);
//System.out.println("");
quicksortMitte(arr2, 0, arr2.length-1);
System.out.println("Pivot-Element Mitte");
arrayAusgebenMitte(arr2);
System.out.println("");
//quicksortMitte(arr2, 0, arr2.length-1);
//System.out.println("Pivot-Element Mitte - Erneutes Sortieren auf dem bereits sortierten Array");
//arrayAusgebenMitte(arr2);
//System.out.println("");
quicksortRandom(arr3, 0, arr3.length-1);
System.out.println("Pivot-Element Random");
arrayAusgebenRandom(arr3);
System.out.println("");
//quicksortRandom(arr3, 0, arr3.length-1);
//System.out.println("Pivot-Element Random - Erneutes Sortieren auf dem bereits sortierten Array");
//arrayAusgebenRandom(arr3);
//System.out.println("");
}
/**
* Die Methode arrayFuellen() befüllt das Array
* mit Random-Werten zwischen 0 und 100
*/
public void arrayFuellen()
{
Random rnd = new Random();
for(int i=0; i<=arr1.length-1; i++)
{
arr1[i] = rnd.nextInt(1000); //liefert eine zufällige Zahl zwischen 0 und 1000
}
}
/**
* Die Methode arrayDuplizieren() vervielfältigt
* das Original-Array
*/
public void arrayDuplizieren()
{
for(int i=0; i<=arr1.length-1; i++)
{
arr2[i] = arr1[i];
arr3[i] = arr1[i];
}
}
void quicksortLinks(int arr[], int left, int right)
{
int index = partition(arr, left, right);
if (left < index - 1)
quicksortLinks(arr, left, index - 1);
if (index < right)
quicksortLinks(arr, index, right);
}
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[left];
while (i <= j)
{
vergleicheLinks++;
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
void quicksortMitte(int arr[], int left, int right)
{
int index = partition2(arr, left, right);
if (left < index - 1)
quicksortMitte(arr, left, index - 1);
if (index < right)
quicksortMitte(arr, index, right);
}
int partition2(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j)
{
vergleicheMitte++;
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
void quicksortRandom(int arr[], int left, int right)
{
int index = partition3(arr, left, right);
if (left < index - 1)
quicksortRandom(arr, left, index - 1);
if (index < right)
quicksortRandom(arr, index, right);
}
int partition3(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
// Vergleichselement pivot
int p1=0, p2=0, p3=0;
int pivot = 0;
Random rnd1 = new Random();
Random rnd2 = new Random();
Random rnd3 = new Random();
if (arr.length<3)
{
pivot = arr[left];
}
if (arr.length>=3)
{
p1 = arr[left+rnd1.nextInt(right-left+1)];
p2 = arr[left+rnd2.nextInt(right-left+1)];
p3 = arr[left+rnd3.nextInt(right-left+1)];
if (p2<p1 && p3>p1 || p2>p1 && p3<p1)
{
pivot = p1;
}
if (p1<p2 && p3>p2 || p1>p2 && p3<p2)
{
pivot = p2;
}
if (p1<p3 && p2>p3 || p1>p3 && p2<p3)
{
pivot = p3;
}
if (p1==p2 || p2==p3 || p1==p3)
{
pivot = p1;
}
}
while (i <= j)
{
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j)
{
vergleicheRandom++;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
/**
* Die Methode arrayAusgeben() gibt die Integer-Werte
* der der Arrays aus.
*
*/
public void arrayAusgebenLinks(int arr[])
{
for(int i=0; i<=arr.length-1; i++)
{
System.out.print(arr[i] + ", ");
}
System.out.println("");
System.out.print("Anzahl der Vergleiche: " +vergleicheLinks);
System.out.println("");
}
public void arrayAusgebenMitte(int arr[])
{
for(int i=0; i<=arr.length-1; i++)
{
System.out.print(arr[i] + ", ");
}
System.out.println("");
System.out.print("Anzahl der Vergleiche: " +vergleicheMitte);
System.out.println("");
}
public void arrayAusgebenRandom(int arr[])
{
for(int i=0; i<=arr.length-1; i++)
{
System.out.print(arr[i] + ", ");
}
System.out.println("");
System.out.print("Anzahl der Vergleiche: " +vergleicheRandom);
System.out.println("");
}
}Ich habe die drei Algorithmen auf einem Array der Größe 10000, mit random Elemente zwischen 0 und 1000, laufen lassen. Ausgabe siehe Anhang
Im Anhang mein BlueJ-Projekt.
Ich würde gerne wissen, ob ich einen Fehler gemacht habe, oder ob das mit der Wahl des Pivot-Elements doch nicht stimmt. (kann ich mir ja eigentlich nicht vorstellen)
viele liebe Grüße,
Deggit
