Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
ich muss nach Weihnachten ein Referat über Quicksort und die Implementierung mit/in Java halten.
Ich hab nun zunächste versucht den Quellcode selbst zu schreiben, aber da Quicksort nur mit Zufallspivotelement gut implementiert ist, bereitet mir das einige Probleme.
Ansich ist das kein Problem.
Zufallspivot finden.
Element mit dem ersten des Array tauschen.
Alle Elemente von 1-n sortieren und am ende Pivot an dir richtige Stelle stecken.
Das kommt mir aber zu kompliziert vor. Es soll ja am ende auch eine "gute" implementierung sein und es geht immerhin um meine Modulnote. Geht es irgendwie OHNE das Pivotelement zunächst an eine andere Stelle zu schieben?
Nächste frage: Wir hatten in der Vorlesung den Pseudocode für eine Quicksort implementierung, die hab ich in java umgesetzt und diese sieht nun wie folgt aus:
Java:
package algorithmen.sort;
public class Quicksort{
public static void quicksort(int[] array, int linkePos, int rechtePos){
if(linkePos < rechtePos){
int i = linkePos;
int j = rechtePos;
int temp;
int pivot = array[(int)(Math.random()*(array.length-1))];
do{
while(array[i] < pivot){
i = i+1;
}
while(array[j] > pivot){
j = j-1;
}
if(i <=j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}while(i <= j);
//quicksort(array, linkePos, j);
//quicksort(array,i,rechtePos);
}
}
}
Meine Frage: Ist das überhaupt noch Quicksort?
Ich dachte der Algorithmus sieht vor das man ein Pivotelement sucht und die Tabellen ordnet indem alles was kleiner/gleich ist nach links kommt und alles was größer/gleich ist nach rechts sodass am Ende das Pivotelement in der Mitte steht und im nächsten Schritt nicht wieder mit Sortiert wird da es ja bereits an der richtigen Stelle ist?
Aber in der Implementierung oben passiert das ja nicht. Wir sortieren zwar anhand eines Pivotelements aber das steht halt irgendwo in dem Array und nicht genau zwischen den beiden Listen. Es wird ja immer wieder mitsortiert und spaltet die Listen nicht in 2 weitere?
Zufallspivot finden.
Element mit dem ersten des Array tauschen.
[...]
Geht es irgendwie OHNE das Pivotelement zunächst an eine andere Stelle zu schieben?
Ehrlich gesagt ist es mir gerade schleierhaft wieso du das Pivotelement ersteinmal an den Anfang des Arrays befördern möchtest. Das Pivotelement ist eigentlich nur ein x-beliebiges* Element aus deinem aktuellen Teilarray. Es ist ganz egal wo es zu Beginn steht, es wird ja im Laufe der Sortierung ohnehin sukkzessive an seine endgültige Position geschoben.
Aber in der Implementierung oben passiert das ja nicht. Wir sortieren zwar anhand eines Pivotelements aber das steht halt irgendwo in dem Array und nicht genau zwischen den beiden Listen. Es wird ja immer wieder mitsortiert und spaltet die Listen nicht in 2 weitere?
Du hast völlig recht. So wie es dort steht ist das Unsinn. Möglicherweise ist der Pseudocode missverständlich formuliert? Poste ihn doch mal hier, wenn du magst.
* die Beliebigkeit gilt bezüglich der Korrektheit des Algorithmuses. Für die Performance macht die Wahl des Pivotelements freilich schon einen Unterschied.
Hmm ich wollte es tauschen weil egal was ich mir überlegt hab immer wieder "mist" rausgekommen ist.
Ich hab es nicht hinbekommen einen Code zu schreiben sodass das Pivot Element immer an der Korrekten Stelle steht.
Vielleicht bin ich ja einfach zu doof...ist halt schwierig wenn man das mal eben aus dem stehgreif machen soll...hab mich jetzt schon echt lange dran gesetzt mit Poker Karten und die per Hand sortiert.
Aber: Sobald i und j sich nähern bekomm ich Probleme. Weil entweder sind i und j gleich dann ist es ja egal welches ich mit dem Pivot tausche. Aber dann gibt es ja fälle an denen i und j sich kreuzen und manchmal steht das Element was ich mit dem Pivot tauschen will an Stelle i und manchmal an Stelle j.
Irgendwas läuft da schief.
Zu dem Pseudocode. Ich weiß nicht ob ich den Posten darf. Weil es ja aus dem Skript vom Prof kommt Uhrheberrecht etc..
Der Code ansich funktioniert auch, es wird geordnet und zwar korrekt und auch egal mit welchen Zahlen.
Aber das Pivotelement wird halt immer wieder mit sortiert und steht halt nicht zwischen den neuen "Teil-Arrays" die Start und Endmarkierung bekommt die rekursion also nicht durch das Pivot element sondern durch die Laufindizes i und j.
Und so hab ich es einfach noch nie gesehen und so ist es auch nirgens beschrieben, also tatsächlich nicht quicksort?
Aber: Sobald i und j sich nähern bekomm ich Probleme. Weil entweder sind i und j gleich dann ist es ja egal welches ich mit dem Pivot tausche. Aber dann gibt es ja fälle an denen i und j sich kreuzen und manchmal steht das Element was ich mit dem Pivot tauschen will an Stelle i und manchmal an Stelle j.
Nein. Was immer es ist, es ist nicht Quicksort. Die obige Implementierung erinnert eher an Moron-Sort: Wir erzeugen solange zufällige Permutationen bis wir die korrekte Sortierung erhalten...
Der obige Code sortiert zwar tatsächlich, aber wenn du mal einen Zähler einbaust, der mitzählt wie häufig die Methode quicksort(...) aufgerufen wird, dann bekommst du sowas heraus:
bei 64 Elementen: 1.400 - 2.900 Aufrufe von quicksort
bei 256 Elementen: 21.000 - 32.000 Aufrufe von quicksort
bei 1024 Elementen: 230.000 - Stack overflow Aufrufe von quicksort
Und das wo Quicksort doch im average case eine Laufzeit von O( n log(n) ) haben sollte...
Am besten du vergisst den Pseudocode aus deinem Skript mal und implementierst das so wie du es für sinnig hälst. Du weisst ja wie das Teil funktionieren soll.
Ok fangen wir mal bei 0 an und vergessen das was oben steht. Ich hab nun mal den WikiPseudocode implementiert, aber vorausgesetzt der ist richtig hab ich nen Fehler gemacht den ich nicht finde, desweiteren funktioniert der auch nur wenn das pivot Element das Element ist, welches rechts aussen steht. Denn am Ende wird mit dem Element getauscht.
Aber hier der Quellcode:
Java:
package algorithmen.sort;
public class Quicksort {
public static void quicksort(int[] array, int linkePos, int rechtePos){
if(linkePos < rechtePos){
int teilPos = partitioniere(array, linkePos, rechtePos);
quicksort(array, linkePos, teilPos-1);
quicksort(array, teilPos+1,rechtePos);
}
}
private static int partitioniere(int[] array, int linkePos, int rechtePos) {
int i = linkePos;
int j = rechtePos;
int temp;
int pivot = array[rechtePos];//array[(int)(Math.random() * (array.length-1))];
do{
while(array[i] <= pivot && i < rechtePos){
i++;
}
while(array[j] >= pivot && j > linkePos){
j--;
}
if(i < j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}while(i<j);
if(array[i] > pivot){
temp = array[i];
array[i] = array[rechtePos];
array[rechtePos] = array[i];
}
return i;
}
}
Der macht leider nicht das was er soll ... ich werd mich gleich nochmal selber dransetzten aber vielleicht kann mir jemand schonmal sagen was hier falsch läuft?
Testprogramm:
Java:
package test;
import algorithmen.sort.Quicksort;
import static einaus.EinAusgabe.*;
public class QuicksortTest{
public static void main(String[] args){
final int STARTWERT = 0;
int[] liste = {5,9,4,6,7,6,2,3,8};
for(int i = 0; i < liste.length; i++){
p(liste[i] + " ");
}
pln();
Quicksort.quicksort(liste,STARTWERT,liste.length-1);
for(int i = 0; i < liste.length; i++){
p(liste[i] + " ");
}
}
}
/**
* Sorts the specified sub-array of integers into ascending order.
*/
private static void sort1(int x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)
swap(x, j, j-1);
return;
}
// Choose a partition element, v
int m = off + (len >> 1); // Small arrays, middle element
if (len > 7) {
int l = off;
int n = off + len - 1;
if (len > 40) { // Big arrays, pseudomedian of 9
int s = len/8;
l = med3(x, l, l+s, l+2*s);
m = med3(x, m-s, m, m+s);
n = med3(x, n-2*s, n-s, n);
}
m = med3(x, l, m, n); // Mid-size, med of 3
}
int v = x[m];
// Establish Invariant: v* (<v)* (>v)* v*
int a = off, b = a, c = off + len - 1, d = c;
while(true) {
while (b <= c && x[b] <= v) {
if (x[b] == v)
swap(x, a++, b);
b++;
}
while (c >= b && x[c] >= v) {
if (x[c] == v)
swap(x, c, d--);
c--;
}
if (b > c)
break;
swap(x, b++, c--);
}
// Swap partition elements back to middle
int s, n = off + len;
s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
// Recursively sort non-partition-elements
if ((s = b-a) > 1)
sort1(x, off, s);
if ((s = d-c) > 1)
sort1(x, n-s, s);
}
[...] desweiteren funktioniert der auch nur wenn das pivot Element das Element ist, welches rechts aussen steht. Denn am Ende wird mit dem Element getauscht.
Ich habe mir zwischenzeitlich mal ein Paper[1] vom Hoare angesehen, und dort schlägt er ein solches Verfahren vor: Das Pivotelement ersteinmal "aus dem Weg räumen", also an das Ende des Arrays verschieben, und dann den Rest des Arrays behandeln. Das kann man so machen, zwangsläufig notwendig ist es allerdings nicht. Die Methode Partition muss ja lediglich sicherstellen das bei ihrer Beendigung die bekannten Bedingungen für das Teilarray erfüllt sind. Ob der von Hoare genannte Weg nun die bestmögliche Lösung für diese Aufgabe darstellt, da kann man sich mal den Kopf drüber zerbrechen wenn man lustig ist.
By the way, was bedeutet denn "gut" in diesem Zusammenhang? Einfach, schnell, speicherplatzsparend oder universell? Oder noch etwas anderes? Zu kompliziert ist der Quicksort in der jetzigen Form jedenfalls nicht.
Und das war/ist mein Problem. Ist das verschieben notwendig? Ist immerhin eine zusätzliche Operation in jedem rekursionsschritt. Ich habe es nicht geschafft das Partitionieren so zu implementieren das es keine Rolle spielt an welcher Stelle das Pivotelement steht.
package algorithmen.sort;
public class Quicksort {
private static final int STARTWERT = 0;
public static void quicksort(int[] array){
quicksort(array, STARTWERT , array.length-1);
}
public static void quicksort(int[] array, int linkePos, int rechtePos){
if(linkePos < rechtePos){
randomPivot(array);
int pivot = partitioniere(array, linkePos, rechtePos);
quicksort(array, linkePos, pivot-1);
quicksort(array, pivot+1,rechtePos);
}
}
private static void randomPivot(int[] array){
int random = (int)(Math.random() * (array.length-1));
vertausche(array, random, array.length-1);
}
private static int partitioniere(int[] array, int linkePos, int rechtePos) {
int i = linkePos;
int j = rechtePos;
int pivot = array[rechtePos];
do{
while(array[i] <= pivot && i < rechtePos){
i++;
}
while(array[j] >= pivot && j > linkePos){
j--;
}
if(i < j){
vertausche(array, i, j);
}
}while(i<j);
if(array[i] > pivot){
vertausche(array, i, rechtePos);
}
return i;
}
private static void vertausche(int[] array, int a, int b){
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
Aber die "randomPivot" Methode funktioniert nicht, dann macht er Quatsch mit der Liste. Ohne gehts aber...ich seh meinen Fehler nicht könnt ihr mir da vll noch auf die Sprüunge helfen?
Ich möchte doch das bei jedem rekursionschritt einer neuer Pivotwert randommäßig gewählt wird um das Eintreten des WorstCase falls möglichst zu eleminieren.
Wenn ich nun aber nur eine Variable mit final habe benutz ich ja durchweg den selben Zufallswert, was im Endeffekt doch das gleiche wäre als wenn ich immer das letzte Element als Pivot wähle?
Und das war/ist mein Problem. Ist das verschieben notwendig? Ist immerhin eine zusätzliche Operation in jedem rekursionsschritt. Ich habe es nicht geschafft das Partitionieren so zu implementieren das es keine Rolle spielt an welcher Stelle das Pivotelement steht.
Also zunächst einmal: Für die Laufzeit werden im Allgemeinen nur die sogenannten "wesentlichen Operationen" gezählt. Beim Sortieren sind das eigentlich immer die Vergleiche von Elementen. Alle anderen Operationen - wie Vertauschen, Zähler anpassen, Funktionsaufrufe etc - werden nicht gewertet (solange kein besonderer Grund dafür vorliegt). Man geht davon aus, das die unwesentlichen Operationen alle hinreichend schnell abgearbeitet werden können, so das die Laufzeit im wesentlichen durch die wesentlichen Operationen (hier also die Vergleiche von Elementen) bestimmt wird. Das mag einem ersteinmal seltsam vorkommen, aber dafür gibt es einen guten Grund: Wir wollen die Performance ja allgemeingültig bestimmen, also unabhängig davon was für Daten wir sortieren. In deinem Beispiel haben wir es mit Integerwerten zu tun, und die lassen sich leicht (und schnell) miteinander vergleichen. Aber der Algorithmus soll ja auch andere Daten - wie zum Beispiel Strings - sortieren können. Und ein Vergleich von zwei Strings (oder noch komplizierteren Dingen) kann durchaus sehr aufwendig sein und lange dauern; viel länger als die unwesentlichen Operationen. Deshalb zählt man halt nur die Anzahl der Vergleiche. Und genau deswegen ist das "wegoptimieren wollen" der anfänglichen Vertauschung der beiden Elemente auch absolut nicht notwendig. Ich an deiner Stelle würde es bleiben lassen und mich eher damit beschäftigen wie man die Anzahl der Vergleiche generell reduzieren kann.
Um aber dennoch auf die Frage zurückzukommen: Pseudocode in Lehrbüchern ist ja schön und gut, er dient aber natürlich nur dazu das Funktionsprinzip zu verdeutlichen. Optimiert ist er in der Regel nicht. Daher solltest du dich von ihm lösen und dir selber eine Methode partitioniere ausdenken. Es gilt folgendes:
- die Methode bekommt ein Array übergeben
- sie soll den Index irgendeines Elements zurückgeben für das gilt: alle Elemente links vom indizierten Element sind kleiner/gleich dem indizierten Element, alle Elemente rechts sind größer/gleich
- die Methode darf das Array verändern
Ob man in der Methode nun zwei Pointer verwendet die von links nach rechts bzw. von rechts nach links wandern oder ob man etwas ganz anderes macht spielt gar keine Rolle. Vergiss den Pseudocode und lass deiner Phantasie freien Lauf.
Ein Beispiel[1] (das zwar auch mit den beiden Pointern arbeitet aber ohne die anfängliche Verschiebung des Pivotelements auskommt) könnte so aussehen:
Java:
public static void quicksort(int[] array, int linkePos, int rechtePos) {
int teilPos = partitioniere(array, linkePos, rechtePos);
if (linkePos < (teilPos - 1))
quicksort(array, linkePos, teilPos - 1);
if (teilPos < rechtePos)
quicksort(array, teilPos, rechtePos);
}
static int partitioniere(int array[], int i, int j) {
int temp;
int pivot = array[ (i+j) / 2 ];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
};
return i;
}
Wenn du noch etwas Code einfügst um die Anzahl der Vergleiche von zwei Elementen des Arrays mitzuzählen wirst du überrascht sein wieviel weniger Vergleiche diese Implementation im Vergleich zu deiner Umsetzung des Pseudocodes benötigt.
Wie schon gesagt, diese Vertauschung spielt für die Performance genau gar keine Rolle. Was aber gerne getan wird um den Quicksort zu beschleunigen ist
- ein "gutes" Pivotelement zu wählen, also ein Element welches das Array möglichst in zwei gleichgroße Teile zerlegt. Häufig schaut man sich dazu drei Elemente des Arrays an und wählt das mittelgroße als Pivotelement. Das ist nicht viel Arbeit und damit lässt sich zumindest der Worstcase vom Quicksort vermeiden.
- wenn die zu sortierenden Teilarrays zu klein werden (sagen wir mal wenn sie weniger als 10 Elemente haben) dann werden diese kleinen Teilarrays nicht mehr mit dem Quicksort weitersortiert sondern man verwendet dafür ein anderes Verfahren (z.B. Shellsort). In der Praxis ist der Quicksort nämlich wegen seines Overheads bei kleinen Arrays leider langsamer als andere Sortierverfahren.
Für dein Referat solltest du dir auf jeden Fall mal einige Paper über die Analyse und Optimierung des Quicksorts anschauen. Zu diesen Themen haben kluge Köpfe ja schon genug geschrieben (z.B. [2], [3] und [4]).
Darüber kann man sich wahrscheinlich streiten. Mir selbst fällt ad Hock aber kein sinvoller Grund ein weshalb man das nicht als statisch deklarieren sollte. Macht die Java-Api ja auch so:
Code:
public static void Arrays.sort(int[] ints)[/c]
Viel Spaß damit! :)
[1] den Code habe ich von hier geklaut: [URL="http://www.algolist.net/Algorithms/Sorting/Quicksort"]Quicksort[/URL]
[2] Ian Parberry: [i]Analysis of Quicksort[/i], 1997 [[URL="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.52.8765&rep=rep1&type=pdf"]Link[/URL]]
[3] Charles Knessl , Wojciech Szpankowski: [i]Quicksort Algorithm Again Revisited[/i], 1999 in Discrete Math. Theor. Comput. Sci., vol. 3, page 43-64 [[URL="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.17.1335&rep=rep1&type=pdf"]Link[/URL]]
[4] Conrado Martínez , Salvador Roura: [i]Optimal Sampling Strategies in Quicksort and Quickselect[/i], 1998 in PROC. OF THE 25TH INTERNATIONAL COLLOQUIUM (ICALP-98), VOLUME 1443 OF LNCS, page 327-338 [[URL="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.17.4954&rep=rep1&type=pdf"]Link[/URL]]
Ich danke euch beiden vor allem dir Dow Jones für deinen echt sehr ausführlichen Beitrag, heute hab ich keine Lust mehr mich damit zu beschäftigen morgen gehts dann weiter. Falls ich dann noch weiterhin Probleme habe melde ich mich hier wieder
Was mir gerade noch so auffällt der Quellcode den du nun gepostet hast, dass ist doch der gleiche den wir auch in unserem Skript stehen haben (nur das statt while eine do while schleife eingesetzt wird)
Aber da haben wir doch festgestellt das es gar kein Quicksort ist weil das Pivotelement gar nicht das Element ist was zurückgegeben wird, oder komm ich nun total durcheinander
Was mir gerade noch so auffällt der Quellcode den du nun gepostet hast, dass ist doch der gleiche den wir auch in unserem Skript stehen haben (nur das statt while eine do while schleife eingesetzt wird)
Aber da haben wir doch festgestellt das es gar kein Quicksort ist weil das Pivotelement gar nicht das Element ist was zurückgegeben wird, oder komm ich nun total durcheinander
Stimmt, jetzt wo du es sagst - das sieht sehr ähnlich aus. Der wesentliche Fehler des Codes in deinem allerersten Posting lag in der Zeile:
Java:
int pivot = array[(int)(Math.random()*(array.length-1))];
Hier wird - wie du ja auch selber feststelltest - das Pivotelement von irgendwo aus dem gesamten Array gewählt, und nicht aus dem aktuellen Teilarray. Das hat zur Konsequenz das der Rest des Algorithmus mit dem falschen Wert irgendwie weiterläuft, aber nicht so wie es der Quicksortalgorithmus vorsieht. Am Ende kommt dann zwar tatsächlich* das sortierte Array heraus (falls er nicht vorher wegen der zufälligen Anzahl von Rekursionen mit einem Stack Overflow abbricht), aber dennoch kann man das kaum als Implementation des Quicksorts bezeichnen. Ich zumindest würde es nicht tun. Und "quick" ist das mit Sicherheit auch nicht...
* Bei meinen Tests war das zumindest so. Ob das immer klappt, und ob der Algorithmus überhaupt terminiert, darüber habe ich jetzt auch keine Lust nachzudenken.
Jetzt muss ich leider doch noch mal auf den Code zurückkommen den du gepostet hast und den ich bereits im Anfangspost erwähnt hab.
Das ich das Pivotelement zufällig gewählt habe spielt überhaupt keine Rolle in dem Algortihmus, auch wenn ich das mittlere Element nehme komme ich zu einem komischen? Ergebnis.
Angenommen ich habe folgende Reihe:
Java:
int[] array={7,6,6,8,5,9,3,4,2}
wird mit deinem/meinem Algotithmus im ersten partitionierungsschritt mit Pivotelement an der (0+9)/2ten Stelle also der 4ten was in diesem Fall "8" ist zu:
Java:
{7,6,6,2,5,4,3,9,8}
Mit der Rückgabe von i=8. (Was in diesem Fall die "9" wäre).
Womit wir nun wieder bei der ursprünmglichen Frage sind: Ist das überhaupt Quicksort?
Wir ordnen zwar das array anhand eines Pivotelements sodass ab index i alle Elemente >=pivot sind und alle Elemente unter i < pivot; Allerdings steht das Pivotelement NICHT an der Stelle i die wir zurückgeben. Und war das nicht das erklärte Ziel?
In diesem Fall würden wir das Array zwar aufteilen und der Algorthmus würde auch Terminieren weil ich ja bei jedem Schritt die Tabelle teile, allerdings verringere ich ja nicht das zu sortierende array um das Pivotelement.
Ich dachte ich partitioniere die Tabelle um das Pivotelement bereits an der korrekten Stelle stehen zu haben um es im nächsten rekursionschritt nicht erneut sortieren zu müssen.
wird mit deinem/meinem Algotithmus im ersten partitionierungsschritt mit Pivotelement an der (0+9)/2ten Stelle also der 4ten was in diesem Fall "8" ist zu:
Java:
{7,6,6,2,5,4,3,9,8}
Mit der Rückgabe von i=8. (Was in diesem Fall die "9" wäre).
Ähm - nein, da hast du entweder einen anderen Algorithmus als ich oder du kommst beim Abzählen durcheinander (Arrayindizes beginnen bei 0). Wir werden das gleich mal durchexzerzieren, zunächst möchte ich aber auf deine andere Frage zu sprechen kommen:
Meiner Ansicht nach ja. Wenn jemand einen Algorithmus "erfindet" und veröffentlich dann ist es gängige Praxis das er dabei erstmal die Funktionsweise beschreibt und anschließend noch Hinweise zu einer möglichen Implementierung (als proof of concept) gibt. Zur Funktionsweise schrieb Hoare:
"The Problem of sorting a mass of items may be reduced to sorting two lesser segments of data, provided that it is known that the keys of each of the items held in locations lower than a certain dividing line are less than the keys of all of the items held in locations above this dividing line. In this case the two segments may be sorted separately, and as a result the whole mass of data will be sorted.
In practice the existance of such a dividing line will be rare, and even if it did exist its position would be unknown. It is, however, quite easy to rearrange the items in such a way that a dividing line is brought into existence, and its position is known. The method of doing this has been given the name partition."
Hoare redet hier also nur von einer abstrakten Grenzlinie (und eine solche liefert unser Algorithmus, wie wir später sehen werden). Wohlgemerkt, es ist hier nicht gefordert, das die Methode partition irgendein Element an seine endgültige Position verschiebt! Davon ist erst später in dem Paper die Rede, und zwar bei den Vorschlägen zu einer möglichen Implementierung: "... An awkward situation is liable to arise if [...]. This may be prevented by the use of a method that ensures that at least one item is placed in its correct position as a result of each application of the partitioning process."
Okay, also bei seinem Vorschlag wie man partition implementieren kann gibt es eine Schwachstelle. Sein Tipp um diese zu umgehen: Partition so schreiben, das immer ein Element an seine endgültige Position wandert.
Nun sind Vorschläge aber eben nur Vorschläge. Wie man es tatsächlich handhabt bleibt einem selbst überlassen (und ohnehin findet man sich häufig mit Begebenheiten konfrontiert für die diese allgemeinen Implementierungsvorschläge suboptimal sind).
Unser Algorithmus hält sich jedenfalls nicht an Hoares Vorschläge zur Implementierung sondern implementiert partition etwas anders, wodurch die Notwendigkeit entfällt eines der Elemente an seine endgültige Position zu schieben. Gleichwohl erfüllt unser partition die Anforderungen, nämlich eine Grenzlinie zu ziehen und das Array dadurch in zwei Teile zu zerlegen (welche die oben genannten Bedingungen erfüllen: Alle Elemente des linken Teilarrays sind kleiner/gleich jedem Element des rechten Teilarrays (und umgekehrt).
Von daher würde ich schon sagen das es sich immer noch um einen Quicksort handelt. Vielleicht nicht um einen lupenreinen Hoare-Quicksort sondern eher um eine Variante, aber immer noch um einen Quicksort. Wer auch immer das so implementiert hat - er sah darin offenbar keine hinreichend große Abweichung vom original Quicksort als das er seiner Implementation einen eigenen Namen gegeben hat (was bei größeren Veränderungen üblich ist, siehe z.B. beim multikey Quicksort oder balanced quicksort).
So, schauen wir uns jetzt mal an was unser Algorithmus (ich poste ihn unten nochmal, nur um sicherzugehen das wir beide den gleichen verwenden) mit deinem Array schönes anstellt. Wir beginnen mit der Folge:
[c] 7, 6, 6, 8, _5_, 9, 3, 4, 2 [/c]
Als Pivotelement wird das Element an Position (0+9)/2 = 4 hergenommen (ich habe es mal unterstrichen). Das vierte Element hat den Wert 5. Partition liefert mir dabei das Array [c]2, 4, 3, 5, 8, 9, 6, 6, 7[/c] und die teilPos 4 zurück (teilPos ist dabei immer der Index des ersten Elements im zweiten Teilarray). Wir erhalten also die Aufteilung:
[c] [ 2, 4, 3, 5 ] [ 8, 9, 6, 6, 7] [/c]
Wie man sieht gibt es hier kein Element "in der Mitte", welches bereits an seine endgültige Position geschoben wurde. Trotzdem sind die von Hoare verlangten Bedingungen erfüllt: Alle Elemente im linken Teil sind kleiner/gleich den Elementen im rechten Teil (und umgekehrt). Somit verhält sich unser partition also genau so wie Hoare es in seiner Funktionsbeschreibung verlangt.
Anmerkung: Da wir zur Teilung das Pivotelement 5 verwendet haben gilt auch: Alle Elemente im linken Teil sind kleiner/gleich dem Pivotelement, alle Elemente rechts sind größer/gleich. Das unser gewähltes Pivotelement (5) hier tatsächlich an seiner endgültigen Position steht ist Zufall und wird von Partition keineswegs gewährleistet (und laut Funktionsbeschreibung ja auch nicht verlangt). Lass dich dadurch nicht auf eine falsche Fährte locken.
Als nächstes behandeln wir das linke Teilarray (ich werde im folgenden immer das gesamte Array zeigen, auch wenn nur die Teile in den eckigen Klammern von interesse sind). Der Index unseres Pivotelements ist (0+3)/2 = 1, der Wert des Elements mit Index 1 ist 4:
[c] [ 2, _4_, 3, 5 ] , 8, 9, 6, 6, 7 [/c]
Partition liefert als Rückgabewert eine 2 (unsere neue Grenzlinie soll also vor dem Element mit Index 2 verlaufen):
[c] [ 2, 3 ] [ 4, 5 ] , 8, 9, 6, 6, 7 [/c]
Auch hier sind die Bedingungen wieder erfüllt: Alles links ist kleiner/gleich rechts und umgekehrt.
Es wird wieder mit dem linken Teilarray fortgefahren. Der Index des Pivotelements ist diesmal (0+1)/2 = 0, der Wert ist 2.
[c] [ _2_, 3 ] , 4, 5, 8, 9, 6, 6, 7 [/c]
Partition liefert nun eine 1 zurück (die Grenzlinie verläuft also vor dem Element mit Index 1):
[c] [ 2 ] [ 3 ] , 4, 5, 8, 9, 6, 6, 7 [/c]
Da die Teilarrays jetzt so klein geworden sind das wir sie nicht weiter aufteilen müssen terminiert diese Rekursion hier und kehrt zum vorhergehenden Zustand zurück. Von dort aus rufen wir quicksort für das (aktuelle) rechte Teilarray auf.
Das rechte Teilarray umfasst die Werte 4 und 5. Der Index des Pivotelements ist hierbei (2+3)/2 = 2, der Wert also 4.
[c] 2, 3, [ _4_, 5 ] , 8, 9, 6, 6, 7 [/c]
Partition liefern als neue Grenzposition eine 3 zurück, woraus sich die neuen Teilarrays ergeben:
[c] 2, 3, [ 4 ] [ 5 ] , 8, 9, 6, 6, 7 [/c]
Auch hier sind wir jetzt fertig und kehren zu einem früheren Rekursionsschritt zurück.
Wir sind gerade beim obersten rechten Teilarray. Pivot hat den Index (4+8)/2 = 6 und den Wert 9.
[c] 2, 3, 4, 5, [ 6, 6, _9_, 8, 7] [/c]
Partition liefert als neue Grenze 6 zurück. Das Array bleibt zufällig unverändert.
[c] 2, 3, 4, 5, [ 6, 6 ] [ 9, 8, 7] [/c]
Wir wenden uns wieder dem linken Teilarray zu. Pivot hat den Index (4+5)/2 = 4 und den Wert 6.
[c] 2, 3, 4, 5, [ _6_, 6 ] , 9, 8, 7 [/c]
Partition liefert als neue teilPos 5.
[c] 2, 3, 4, 5, [ 6 ] [ 6 ] , 9, 8, 7 [/c]
Nun ist auch dieser Zweig abgeschlossen.
Als nächstes kommt wieder ein rechtes Teilarray dran. Pivot hat den Index (6+8)/2 = 7, Wert 8.
[c] 2, 3, 4, 5, 6, 6, [ 9, _8_, 7 ] [/c]
Partition liefert als neue Grenze den Index 8.
[c] 2, 3, 4, 5, 6, 6, [ 7, 8 ] [ 9 ] [/c]
Wir rufen wieder partition für das linke Teilarray auf. Pivot hat den Index (6+7)/2 = 6, Wert 7...
[c] 2, 3, 4, 5, 6, 6, [ _7_, 8 ] , 9 [/c]
...und liefert den Index 7 als neue Grenze zurück.
[c] 2, 3, 4, 5, 6, 6, [ 7 ] [ 8 ] , 9 [/c]
Die Teilarrays umfassen nur noch 1 Element, und somit endet die Rekursion hier.
Anschließend wird das rechte Teilarray betrachtet:
[c] 2, 3, 4, 5, 6, 6, 7, 8, [ 9 ] [/c]
Da es aber auch nur ein Element groß ist wird es nicht weiter behandelt. Der Quicksort ist fertig.
[...] In diesem Fall würden wir das Array zwar aufteilen und der Algorthmus würde auch Terminieren weil ich ja bei jedem Schritt die Tabelle teile, allerdings verringere ich ja nicht das zu sortierende array um das Pivotelement.
Ich dachte ich partitioniere die Tabelle um das Pivotelement bereits an der korrekten Stelle stehen zu haben um es im nächsten rekursionschritt nicht erneut sortieren zu müssen.
Beides. Man kann es so machen, das man ein Pivotelement an die korrekte Stellt schiebt. Man kann es aber auch anders machen und trotzdem noch der von Hoare beschriebenen Funktionsweise des Quicksorts folgen. Erst wenn man sich eine signifikante Verbesserung des Originalverfahrens ausgedacht hat würde man das ganze als Quicksort-Variante betrachten und ihr einen eigenen Namen geben (Schmidtscher quicksort oder sowas) um ihn vom Original zu unterscheiden. In unserem Fall trifft das aber imho nicht zu. In meinen Augen ist unsere Implementation immer noch ein normaler Quicksort.
Ich hoffe das hilft dir etwas weiter.
PS: Und da ich sie ja auch noch mal posten wollte:
Java:
public static void quicksort(int[] array, int linkePos, int rechtePos) {
int teilPos = partition(array, linkePos, rechtePos);
if (linkePos < (teilPos-1))
quicksort(array, linkePos, teilPos-1);
if (teilPos < rechtePos)
quicksort(array, teilPos, rechtePos);
}
static int partition(int array[], int i, int j) {
int temp;
int pivot = array[(i+j) / 2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
return i;
}
Ähm - nein, da hast du entweder einen anderen Algorithmus als ich oder du kommst beim Abzählen durcheinander (Arrayindizes beginnen bei 0). Wir werden das gleich mal durchexzerzieren
Ja du hast recht, ich hab mich verzählt. Das Funktionsprinzip ist allerdings klar auch das die beiden Teilarrays die Bedingungen erfüllen größer/gleich und kleiner/gleich dem Pivot zu sein.
Nun hat sich auch die Frage geklärt ob es sich noch um Quicksort handelt, danke dafür
Ich werd mir gleich nochmal einen Zähler einbauen der die Vergleiche für beide Varianten mitzählt weil wenn ich mir die Algorithmen so angucke und darauf zurückkomme was du bereits weiter oben erwähnt hast, dass nur die wesentlichen Operationen gezählt werden, kommt mir der Quicksort mit dem Zufallselement nach rechts schieben, ordnen, pivot zurückgeben performanter vor.
Immerhin fällt ein vergleich raus da das Pivotelement bereits sortiert ist, es muss ja nicht nochmal verglichen werden.
Aber dann hat sich nun endlich alles geklärt=) Und ich danke dir vielmals für deine Mühe, allein der letzte Post war sicher zeitaufwendig genug.
Ich werd mir gleich nochmal einen Zähler einbauen der die Vergleiche für beide Varianten mitzählt weil wenn ich mir die Algorithmen so angucke und darauf zurückkomme was du bereits weiter oben erwähnt hast, dass nur die wesentlichen Operationen gezählt werden, kommt mir der Quicksort mit dem Zufallselement nach rechts schieben, ordnen, pivot zurückgeben performanter vor.
Und was kommt dabei heraus? Poste deine Forschungsergebnisse mal hier, ich bin mir sicher das es noch mehr Menschen gibt das interessiert.
Da du ja ein Referat schreiben sollst möchte ich dir aber noch in Erinnerung rufen das die Vergleiche von zwei Elementen in der Regel zwar pauschal als wesentliche Operationen angenommen werden, es aber keineswegs sein müssen. Es kann durchaus sinnvoll sein andere Operationen als wesentlich zu betrachten, zum Beispiel die Zugriffe auf ein Element. Wenn die Daten in einem externen Speicher liegen (z.B. jedes einzeln aus einer Datenbank abgefragt werden muss) oder in einer Datenstruktur mit nicht wahlfreiem Zugriff liegen (z.B. in einer Liste), dann würde man vielleicht eher die Zugriffe auf die Elemente als wesentliche Operationen betrachten, halt weil die Zugriffe viel länger dauern als die Vergleiche. Dementsprechend könnte man die Implementierung des Quicksorts anpassen. Oder ggf. einen anderen Sortieralgorithmus wählen, der mit weniger Zugriffen auskommt. Untersuche das doch auch mal, damit kannst du sicherlich noch ein ganzes Kapitel des Referats füllen (aber sei gewarnt, die Theroretiker bestehen auf den Vergleichen als wesentliche Operationen... ).
Falls du die Performance des Quicksorts dabei auch mit anderen Sortieralgorithmen vergleichen möchtest: Hier findest du die Quellcodes für eine ganze Reihe von Sortierverfahren in Java.
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:
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());
}
}
Quicksort mit Pivotelement nach Patitionierung zwischen Teillisten
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;}
}
Und der Quicksort wo an anderer Stelle getrennt wird:
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;}
}
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:
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.
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.
[Java]
private static int randomPivot(int[] array, int linkePos, int rechtePos){
int pivot = array[(int)(Math.random() * (rechtePos-linkePos)+linkePos)];
vertausche(array, pivot, rechtePos);
[/code]
Kann es sein das du hier den Index des Pivotelements mit seinem Wert verwechselst?
Ich habe mich ebenfalls mal darangesetzt die Anzahl der Vergleiche - allerdings nur die Vergleiche zwischen zu sortierenden Elementen - zu zählen, und herausgekommen ist das hier (sind einige Diagramme, daher als ZIP-Archiv): Click. Vielleicht kannst du auch etwas damit anfangen.
Ja ich habe mittlerweile den Fehler auch schon entdeckt und auch die Vergleiche bereits auf die Arrayelemente beschränkt.
Es fällt schon sehr deutlich auf das die eine Variante "geringfügig" weniger Vergleiche benötigt(Wenn man die Laufindizes nach vertauschen direkt erhöht) dafür aber eine deutlich höhere rekursionstiefe hat.
Danke für die Diagramme die helfen sicher auch nochmal
