Ja natürlich gerne
Und nur mal eben nebenbei: Ich muss zwar ein Referat halten aber das muss nicht sonderlich tiefgründig sein, ist mehr persönliches Interesse gewesen und falls mein Prof nachfragt damit ich passende Lösungen habe. Das Referat ist an Erstsemester gerichtet und ist nur ein kurzreferat von 10min
Ich möchte hier nochmal den Quelltext posten.
1. Weil ich mit der Zufallspivot Methode immernoch Probleme hab, ich nehm momentan immer das rechte Element und versteh nicht warum es duch zufall nicht geht.
2. Damit ihr drübergucken könnt eventuell Fehler aufdecken könnt die ich eventuell beim Einbau der Counter gemacht hab. Das ganze ist nicht unbedingt Lupenrein programmiert. Ist auch nur für Testzwecke.
Testprogramm:
[code=Java]package test;
import static algorithmen.sort.Quicksort.*;
import static algorithmen.sort.QuicksortLautInformatikSkript.*;
import static einaus.EinAusgabe.*;
public class QuicksortTest{
public static void main(String[] args){
//Hier die Anzahl der Arrayelemente ändern
int laenge = 20;
//***************************************
int[] liste = new int[laenge];
int[] liste1 = new int[laenge];
for(int i = 0; i<laenge; i++){
liste[i] = (int)(Math.random() * (laenge-1));
}
System.arraycopy(liste, 0, liste1, 0, liste.length);
//Ausgabe Original Array
p("Ursprungsreihenfolge: ");
for(int i = 0; i < liste.length; i++){
p(liste[i] + " ");
}
pln();
//Sortiere Array 1 und gib es aus
quicksort(liste);
p("Sortiert Pivot Zufaellig: ");
for(int i = 0; i < liste.length; i++){
p(liste[i] + " ");
}
pln();
pln("Vergleiche Pivot Zufaellig: " + getAnzahlVergleiche());
pln("Anzahl Aufrufe Pivot Zufaellig: " + getAnzahlAufrufe());
//Sortiere Array 2 und gib es aus
sortiere(liste1,0,liste1.length-1);
p("Sortiert Pivot mitte: ");
for(int i = 0; i < liste1.length; i++){
p(liste1[i] + " ");
}
pln();
pln("Vergleiche Pivot mitte: " + getAnzahlVergleich());
pln("Anzahl Aufrufe Pivot mitte: " + getAnzahlRekursion());
}
}[/code]
Quicksort mit Pivotelement nach Patitionierung zwischen Teillisten
[code=Java]package algorithmen.sort;
public class Quicksort {
private static int anzahlVergleiche = 0;
private static int anzahlAufrufe = 0;
public static void quicksort(int[] array){
quicksort(array, 0 , array.length-1);
}
public static void quicksort(int[] array, int linkePos, int rechtePos){
if(linkePos < rechtePos){
int pivot = partitioniere(array, linkePos, rechtePos);
quicksort(array, linkePos, pivot-1);
quicksort(array, pivot+1,rechtePos);
}
anzahlVergleiche ++;
anzahlAufrufe++;
}
private static int randomPivot(int[] array, int linkePos, int rechtePos){
int pivot = array[(int)(Math.random() * (rechtePos-linkePos)+linkePos)];
vertausche(array, pivot, rechtePos);
return pivot;
}
private static int partitioniere(int[] array, int linkePos, int rechtePos) {
int i = linkePos;
int j = rechtePos;
int pivot = array[rechtePos];//randomPivot(array,linkePos, rechtePos);
do{
while(array[i] <= pivot && i < rechtePos){
i++;
anzahlVergleiche++;
}
anzahlVergleiche++;
while(array[j] >= pivot && j > linkePos){
j--;
anzahlVergleiche++;
}
if(i < j){
vertausche(array, i, j);
}
anzahlVergleiche ++;
}while(i<j);
anzahlVergleiche++;
if(array[i] > pivot){
vertausche(array, i, rechtePos);
}
anzahlVergleiche++;
return i;
}
private static void vertausche(int[] array, int zahlA, int zahlB){
int temp = array[zahlA];
array[zahlA] = array[zahlB];
array[zahlB] = temp;
}
public static int getAnzahlVergleiche(){ return anzahlVergleiche;}
public static int getAnzahlAufrufe(){ return anzahlAufrufe;}
}[/code]
Und der Quicksort wo an anderer Stelle getrennt wird:
[code=Java]package algorithmen.sort;
public class QuicksortLautInformatikSkript{
private static int anzahlVergleiche;
private static int anzahlAufrufe;
public static void sortiere(int[] array, int linkePos, int rechtePos){
if(linkePos < rechtePos){
int i = linkePos;
int j = rechtePos;
int temp;
int pivot = array[(i+j) / 2];
do{
while(array[i] < pivot){
i = i+1;
anzahlVergleiche++;
}
anzahlVergleiche++;
while(array[j] > pivot){
j = j-1;
anzahlVergleiche++;
}
if(i <=j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
anzahlVergleiche++;
}while(i <= j);
anzahlVergleiche++;
sortiere(array, linkePos, j);
sortiere(array,i,rechtePos);
}
anzahlAufrufe++;
anzahlVergleiche++;
}
public static int getAnzahlVergleich(){ return anzahlVergleiche;}
public static int getAnzahlRekursion(){ return anzahlAufrufe;}
}
[/code]
So was mir noch Auffällt das ich den einen algorithmus noch optimieren kann indem ich die Indizeszähler nach dem vertauschen erhöhe somit muss ich nicht doppelt die Elemente vergleichen die ich bereits getauscht hab. Hier mal einige Ergebnisse:
5. Elemente
[code=Java]Ursprungsreihenfolge: 3 3 0 1 3
Sortiert Pivot Zufaellig: 0 1 3 3 3
Vergleiche Pivot Zufaellig: 32
Anzahl Aufrufe Pivot Zufaellig: 7
Sortiert Pivot mitte: 0 1 3 3 3
Vergleiche Pivot mitte: 28
Anzahl Aufrufe Pivot mitte: 9
[/code]
10. Elemente
[code=Java]Ursprungsreihenfolge: 2 3 5 4 2 3 1 8 5 0
Sortiert Pivot Zufaellig: 0 1 2 2 3 3 4 5 5 8
Vergleiche Pivot Zufaellig: 74
Anzahl Aufrufe Pivot Zufaellig: 13
Sortiert Pivot mitte: 0 1 2 2 3 3 4 5 5 8
Vergleiche Pivot mitte: 60
Anzahl Aufrufe Pivot mitte: 15
[/code]
50. Elemente
[code=Java]Ursprungsreihenfolge: 1 39 0 27 ....
Sortiert Pivot Zufaellig: 0 0 0 1 ....
Vergleiche Pivot Zufaellig: 553
Anzahl Aufrufe Pivot Zufaellig: 71
Sortiert Pivot mitte: 0 0 0 1 ....
Vergleiche Pivot mitte: 430
Anzahl Aufrufe Pivot mitte: 75
[/code]
100. Elemente
[code=Java]Ursprungsreihenfolge: 98 50 14 89 ....
Sortiert Pivot Zufaellig: 3 6 6 7 ....
Vergleiche Pivot Zufaellig: 1338
Anzahl Aufrufe Pivot Zufaellig: 139
Sortiert Pivot mitte: 3 6 6 7 ....
Vergleiche Pivot mitte: 1207
Anzahl Aufrufe Pivot mitte: 165[/code]
1000. Elemente
[code=Java]Ursprungsreihenfolge: 315 240 863 48 ....
Sortiert Pivot Zufaellig: 0 3 4 4 ....
Vergleiche Pivot Zufaellig: 19691
Anzahl Aufrufe Pivot Zufaellig: 1407
Sortiert Pivot mitte: 0 3 4 4 ....
Vergleiche Pivot mitte: 16705
Anzahl Aufrufe Pivot mitte: 1715
[/code]
Was einem schon stark auffällt ist das die Anzahl Vergleiche bei Algorithmus 1. viel höher ausfällt dafür die Rekursionstiefe deutlich geringer ist.
Wenn ich nun im Laufinidzes im Tauschschritt von Algorithmus 1 auch um 1 erhöhe respektive senke somit reduzier ich auch die Anzahl vergleiche zumindest um 1.
Allerdings wäre dann ja immernoch Algorithmus 2 besser weil die Vergleiche nach wie vor geringer wären, obwohl dieser früher zu einem Stack Overflow führen würde.
Soweit erstmal die Ergebnisse, vielleicht kann mir noch jemand sagen warum das mit dem Zufallspivot nicht funktioniert.
Ergänzung// Wenn ich die Laufindizes in Algorithmus 1 erhöhe beim vertauschen senke ich die Vergleiche drastisch. Habs jetzt ein paar mal laufen lassen die Differenz zu Algorithmus 2 berträgt circa ~ 100-1000 Vergleiche.
Und das wenn das Pivot stets das letzte Element der zu sortierenden Liste ist. Wenn jetzt noch die Zufallspivotwahl funktionieren würde, wäre die Differenz eventuell noch geringer.
