Quicksort Algo in den Folien

Kernel Panik
Erstie
Erstie
Beiträge: 11
Registriert: 31. Jan 2007 14:54

Quicksort Algo in den Folien

Beitrag von Kernel Panik »

in der heutigen Übung mussten wir leider feststellen, dass eine erfolgreiche Sortierung mit dem Algorithmus aus den Vorlesungsfolien nicht möglich ist...
um meine Inkompetenz auszuschließen bitte ich das zu prüfen...

sonothar
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 26. Okt 2005 00:15

Beitrag von sonothar »

das haben wir auch gemerkt. aber nach dem algo im härder funktioniert das
Bild

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

Beitrag von giftnudel »

Was genau soll da nicht gehen?

Kernel Panik
Erstie
Erstie
Beiträge: 11
Registriert: 31. Jan 2007 14:54

Beitrag von Kernel Panik »

gaube für eine eingabelänge von 5 oder 6 werten gabs eine ArrayIndexOutOfBounceException...
mein eigentliches Problem bestand darin, dass ich bei der Anwendung des Codes auf die Aufgabe in der Übung, das N nicht in die größere Liste getauscht habe... habe mitlerweile geschnallt, dass sie das pivot hier ja anders wählen als wir in der Übung, dennoch sollte es doch möglich sein, eine funktionierende while-Konstruktion anzugeben, die immer funktioniert, egal wo das Pivot steht...

z.b für den Aufruf mit: int[] input = {5,9,4,2,12,1};

Benutzeravatar
vwm
Mausschubser
Mausschubser
Beiträge: 94
Registriert: 7. Mai 2007 09:42
Wohnort: Rodenbach

Beitrag von vwm »

Fehler haben sich da eingeschlichen, das ist wahr. Der Algorithmus auf Folie 24 widerspricht dem auf Folie 19, da die Mengen L1 und L2 unterschiedlich aufgebaut werden. Aber meines Erachtens nach funktioniert der abgebildete Algorithmus. Auch für dein Beispiel @ Kernel Panik.

Durchexerziert:
-> 5 9 4 2 12 1
Schritt 1: Pivot = 5, vertauscht werden 9 und 1, danach: i zeigt auf 12, j auf 2.
-> Pivot wird mit j vertauscht und es wird bei j partitioniert: 2 1 4 | 5 | 12 9 (links und rechts gültig)
Schritt 2a: Pivot = 2, vertauscht wird nichts, danach: i zeigt auf 4, j auf 1.
-> Pivot wird mit j vertauscht und es wird bei j partitioniert: 1 | 2 | 4 (links und rechts ungültig)
Schritt 2b: Pivot = 12, vertauscht wird nichts, danach: i zeigt hinter das array, j auf 12.
-> Pivot wird mit j vertauscht und es wird bei j partitioniert: 9 | 12 | - (links und rechts ungültig)
Resultat: 1 2 4 5 9 12.
Zuletzt geändert von vwm am 3. Jul 2007 17:19, insgesamt 1-mal geändert.

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Beitrag von Edoat »

gaube für eine eingabelänge von 5 oder 6 werten gabs eine ArrayIndexOutOfBounceException...
Das lässt sich ganz einfach beheben, statt (i <= j) und (j >= i) nach dem Array Zugriff zu überprüfen (da ist das Kind dann schon in den Brunnen gefallen) muss vorher überprüft werden, also statt:

while ((s <= p) && (i <= j)) i++;
while ((s [j] > p) && (j >= i)) j--;

wie es in den Folien steht, muss es so heißen:

while ((i <= j) && (s <= p)) i++;
while ((j >= i) && (s [j] > p)) j--;

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

Kann mir jemand sagen, warum es in manchen Faellen zu einem StackOverflow kommt?
Das Problem tritt nicht immer auf, aber scheinbar bei bestimmten Eingabemengen kommt es scheinbar zu einer Endlosschleife...

[glow=red]Fehlermeldung:[/glow]
[shadow=grey]Exception in thread "main" java.lang.StackOverflowError
at java.util.ArrayList.get(Unknown Source)
at Quicksort.quicksort(Quicksort.java:24)
at Quicksort.quicksort(Quicksort.java:46)
at Quicksort.quicksort(Quicksort.java:46)
at Quicksort.quicksort(Quicksort.java:46)
....
....
....
at Quicksort.quicksort(Quicksort.java:46)
at Quicksort.quicksort(Quicksort.java:46)[/shadow]





[php]
import java.util.ArrayList;

/**
* The class Quicksort implements the quicksort algorithm
*/
public class Quicksort<E extends Comparable<E>> {

/**
* Sorts a List by using quicksort.
* @param unsorted a (potentially) unsorted list of elements
* @return the sorted list with all elements from unsorted
*/
public ArrayList<E> sort(ArrayList<E> unsorted) {
quicksort(unsorted, 0, unsorted.size()-1, 0);
return unsorted;
}

private void quicksort(ArrayList<E> list, int left, int right, int pivotPosition) {
if(left >= right) return;

// Initialize
int goUp = left;
int goDown = right;
E pivot = list.get(pivotPosition);

while(goUp < goDown) {
// "goUp" moves up the list until an element bigger than pivot is found.
while(goUp<goDown && list.get(goUp).compareTo(pivot) <= 0)
goUp++;
// "goDown" moves down the list until an element smaller or equal to pivot is found.
while(list.get(goDown).compareTo(pivot) > 0)
goDown--;
// Swap the found elements.
if(goUp<goDown){
E swap = list.get(goUp);
list.set(goUp, list.get(goDown));
list.set(goDown, swap);
}
}

if(goUp == goDown){
// Case1: "goUp" and "goDown" point to an element smaller than pivot.
E swap = list.get(goUp);
list.set(goUp, list.get(pivotPosition));
list.set(pivotPosition, swap);
if(left <(goUp-1)) quicksort(list, left, goUp-1, left);
if((goUp+1)<right) quicksort(list, goUp+1, right, goUp+1);
} else {
// Case2: "goUp" points to an element bigger than pivot and goDown is at position "goUp" -1.
E swap = list.get(goDown);
list.set(goDown, list.get(pivotPosition));
list.set(pivotPosition, swap);
if(left <(goDown-1)) quicksort(list, left, goDown-1, left);
if((goDown+1)<right) quicksort(list, goDown+1, right, goDown+1);
}
}
}
[/php]

neffs
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 16. Okt 2006 19:07
Kontaktdaten:

Beitrag von neffs »

Twister11 hat geschrieben:Kann mir jemand sagen, warum es in manchen Faellen zu einem StackOverflow kommt?
hab mir jetzt deinen code nicht durchgelesen, aber ich hatte das auch, immer wenn 2x die gleiche zahl vorkommt.
bin dann auf bubblesort umgestiegen, der funktioniert so wie er in den folien steht.
viel erfolg noch!

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

joa, hab das mehr oder weniger komplett neu geschrieben, daher k.a. ob die Lösung dann auch noch auf die Version im Skript passt:

Wenn die Elemente an stelle i und j gleich sind ->
statt austauschen der Elemente einfach i++ und j--

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Beitrag von bruse »

Ich würde mal drauf tippen, dass beim

Code: Alles auswählen

  // "goDown" moves down the list until an element smaller or equal to pivot is found.
            while(list.get(goDown).compareTo(pivot) > 0)
                goDown--;
vergessen wurde, darauf zu prüfen, dass man nicht links aus dem Array fliegt. Bei einer einelementigen Menge kann das passieren, und dann wird diese Menge recht oft neu sortiert. Ist jedenfalls mein Verdacht.

Einfach mal den Code mit Debug output zupflastern und schauen, wo es hakt. Bubblesort ist jedenfalls eine schlechte Wahl, da wirst du deinem Tutor aber was zu erzählen haben ;-)

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

Nein, denn "goUp" wandert mindestens ein Feld nach Rechts und "goDown" maximal ein Feld an "goUp" vorbei, weshalb das nicht passieren kann.

Der Quicksort funktioniert ausserdem und sortiert Listen mit einigen hundert oder tausend Elementen problemlos.
Allerdings bei Megen von ca. 10.000 oder 50.000 oder mehr Elementen kommt es zu einem StackOverflow.

Das ganze passiert merkwuerdigerweise bei Strings nicht oder sehr viel seltener als bei Double's, ...wobei es ja hier haeufig dazu kommen koennte, dass nur "gleiche" Elemente in der Liste stehen.

Ich hab gehoert, dass die JVM schon so ca 1024 Rekursionsschritte packt, bevor sie am Rad dreht... das heisst aber, dass es kein Problem sein sollte solche Mengen zu bearbeiten.

Abgesehen davon wuerde ich gerne mal den angeblich so tollen Sortieralgorithmus sehen, der Collection.sort() schlaegt... vielleicht koennte RomanSoldier den mal online stellen nach dem Praktikum.

Ansonsten waere ich fuer weitere Hilfe dankbar, denn im Prinzip ist der Quicksort meiner Meinung nach einwandfrei :)

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

Ah ok, ich glaub ich habs verstanden.
Im worst case, wobei es auch schon in Faellen die nur teilweise wie der worst case sind vorkommen kann, ist die Eingabeliste so geartet, dass die Liste so geteilt wird, dass sie pro REKURSIONSSCHRITT nur um ein Feld schrumpft....

zb. Alle Elemente sind gleich. zb. 4 4 4 4 4 4 4 4 4 4 4 ..... 4
dann wandert goUp hoch bis es die Laenge der Liste erreicht und goDown nicht runter.
Dadurch passiert es, dass anschliessend die Liste vor dem letzten Feld geteilt wird.
usw... usw...
dadurch sind natuerlich schnell 1024 Rekursionsschritte ueberwunden und es kommt
zum StackOverflow.
Jemand ne idee wie man solche WorstCases vermeiden kann?
Denke es koennte noch mehr Faelle geben in denen etwas aehnliches passiert.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Worst cases von QuickSort sind halt nun mal worst cases ;) Da kannst du nicht viel drehen. Das ist für das Praktikum aber hier auch irrelevant. Du kannst höchstens kleine Teilprobleme an Insertion Sort abgeben, das spart ein paar Rekursionsschritte an den Enden.

Falls du wirklich viel Elan hast, google mal nach IntroSort. Das ist QuickSort, aber mit einem Rekursionslimit. Wird das Rekursionslimit überschritten, gibt es das Problem an HeapSort ab. Damit hat es im Allgemeinen die gute Laufzeit von QuickSort, garantiert aber im worst case O(nlgn). Hieße aber halt, dass du auch gleich noch einen HeapSort dazu implementieren müsstest ;)

Edit: Ach ja, es gibt noch eine Optimierungsmöglichkeit für die worst cases, wie du sie beschrieben hast: Du kannst einen von zwei Rekursionsverzweigungen vermeiden, wenn du in der Quicksort-Funktion zusätzlich eine Schleife einbaust. Dann kannst du nach der Partitionierung ein Teilproblem rekursiv weitergeben, das andere bleibt aber hier und wird in der Schleife weiter verarbeitet (obere bzw. untere Grenze entsprechend anpassen). Wenn du es geschickt machst, gibst du natürlich immer nur das kleinere Teilproblem per Rekursion weiter. In deinem worst case oben also immer das einzelne Glied, womit du den Stack Overflow effektiv auch eliminierst.

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

Mist, ein zufaelliges Element als Pivot waehlen schafft leider keine Abhilfe.
Das Problem ist nicht beseitigbar glaube ich.

Weil grade beim ProxMapSort bei Doubles die aus Integern gewonnen werden,
bei sehr vielen Elementen (zb. 50.000) im Schnitt in jedem Bucket von 100 Stk.
500 Elemente landen. Spaetestens ab 100.000 Elementen dann im Schnitt wohl ca. 1000 Elemente.

Nun ist aber in jedem 500 bzw 1000 elementigen Bucket dann nur GLEICHE ELEMENTE enthalten. zb. 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 .... usw...

Dieser Fall kommt also dann quasi Standardmaessig vor.
Also schafft auch ein zufaellig gewaehlter Pivot keine Abhilfe.
Jemand ne alternative Idee?
Weil im normalfall sollte durch den zufaellig gewaehlten Pivot kein StackOverFlow eintreten.

[php]
public class Quicksort {

/**
* Sorts a List by using quicksort.
* @param unsorted a (potentially) unsorted list of elements
* @return the sorted list with all elements from unsorted
*/
public static <E extends Comparable<E>> List<E> sort(List<E> unsorted) {
if(unsorted.size() <= 1) return unsorted;
quicksort(unsorted, 0, unsorted.size()-1, calculatePivot(unsorted, 0, unsorted.size()-1));
return unsorted;
}

/**
* Calculates a new pivot element.
* @param small the new left border
* @param big the new right border
* @return the calculated pivot for next recursion.
*/
private static <E extends Comparable<E>> int calculatePivot(List<E> list, int small, int big) {
return small+((int)Math.random())%(big-small);
// return ((list.get(small)).compareTo(list.get(big)) <=0) ? big : small;
}

private static <E extends Comparable<E>> void quicksort(List<E> list, int left, int right, int pivotPosition) {
// Initialize
E pivot = list.get(pivotPosition);
int goUp = left;
int goDown = right;
E swap;
int nextPivot;

while(goUp <= goDown) {
// "goUp" moves up the list until an element bigger than pivot is found.
while(list.get(goUp).compareTo(pivot) < 0) goUp++;
// "goDown" moves down the list until an element smaller or equal to pivot is found.
while(list.get(goDown).compareTo(pivot) > 0) goDown--;

if(goUp<=goDown){
// Swap the found elements.
swap = list.get(goUp);
list.set(goUp, list.get(goDown));
list.set(goDown, swap);
goUp++;
goDown--;
}
}

if(left < (goDown)) { // left side
nextPivot = calculatePivot(list, left, goDown);
quicksort(list, left, goDown, nextPivot);
}
if(goUp < right) { // right side
nextPivot = calculatePivot(list, goUp, right);
quicksort(list, goUp, right, nextPivot);
}
}
}
[/php]
Zuletzt geändert von Twister11 am 5. Jul 2007 06:00, insgesamt 3-mal geändert.

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

Ja wenn ich anfange da irgendwie am Quicksort noch andere Sorts reinzuwursten, dann kann ich es auch gleich sein lassen und direkt MergeSort benutzen.

Antworten

Zurück zu „Archiv“