QuickSort

[gd12]

Ich sollte das QuickSort-Verfahren programmieren, doch leider funktioniert der Algorithmus nicht. Bitte um Hilfe!

Diese Methode wird von der Test-Klasse aufgerufen.
[HIGHLIGHT="Java"]
public <T extends Comparable<T>> void sort(T[] list) {
qsort(list, 0, list.length - 1);
}
[/HIGHLIGHT]


[HIGHLIGHT="Java"]
protected <T extends Comparable<T>> void qsort(T[] list, int u, int o) {
if (o > u) {
int i = zerlege(list, u, o);
qsort(list, u, i - 1);
qsort(list, i + 1, o);
}
[/HIGHLIGHT]


[HIGHLIGHT="Java"]
private <T extends Comparable<T>> int zerlege(T[] list, int u, int o) {
int p = (u + o) / 2;
while (u <= o) {
int l = u;
int r = p + 1;
for (int i = u; i < p - 1; i++) {
if (list.compareTo(list[p]) >= 0) {
l = i;
break;
}
}
for (int i = p + 1; i < o; i++) {
if (list.compareTo(list[p]) < 0) {
r = i;
break;
}
}
if (l <= r) {
vertausche(list, l, r);
u = l + 1;
o = r - 1;
}
}
return o;
}
[/HIGHLIGHT]


[HIGHLIGHT="Java"]
private <T> void vertausche(T[] list, int l, int r) {
T temp = list[l];
list[l] = list[r];
list[r] = temp;
}
[/HIGHLIGHT]

 

[SlaterB]

definiere 'nicht funktionieren', Fehlermeldung oder falsche Sortierung?
bei letzterem poste doch die möglichst kurze Beispiel-Liste dazu,

dann kann jeder die gleichen Tests durchführen,
wobei du dann eigentlich auch selber Schritt für Schritt schauen könntest, was falsch läuft

gehe auf Papier durch, wie die Liste in jedem Schritt zu zerlegen ist, wie die Teillisten sortiert aussehen müssen usw.,
vergleiche in gewissen Abständen die korrekte Vorgabe mit Logausgaben in deinem Programm und finde so genau die Stelle raus, die etwas anders macht

 

[0x7F800000]

würd's dir grad was ausmachen ein einzelnes kompilierbares beispiel zu basteln?
Die neue Forumsoftware ist stets recht buggy, keine lust diese vier trümmerteilchen einzeln aus dem Zitat-text rauszufummeln

 

[gd12]

Okay, das Ganze kann hier geladen werden:
RapidShare: Easy Filehosting

 

[0x7F800000]

manoman... nächstes mal bitte einfach code posten, bitte^^ Habe alleine fürs runterladen des codes um die zwanzig clicks gebraucht omfg...

Also, ich hab da ein wenig rumgespielt, da ist folgendes draus geworden:
[HIGHLIGHT="Java"]
import java.util.Arrays;


public class Quicksort2 /*implements Whatever*/{
public <T extends Comparable<T>> void sort(T[] array) {
qsort(array, 0, array.length);
}

protected <T extends Comparable<T>> void qsort(T[] array, int start, int end) {
if (end-start>1) {
int divisor = divide(array, start, end);
qsort(array, start, divisor);
qsort(array, divisor, end);
}
}

private <T extends Comparable<T>> int divide(T[] array, int start, int end) {
//normalerweise nimmt man zufallszahl, oder bestimmt pivot als median vom ersten mittleren letzte o.ä.
int pivotIndex = (start + end) / 2;
T pivot=array[pivotIndex];

//deine lösung mit 3 verschachtelten schleifen finde ich voll brainfuck
//mir gefällt die hier irgendwie besser:

swap(array,start,pivotIndex); //pivotelement ganz nach links schieben

int rightSideStart=start+1; //dieser index markiert die grenze zwischen links und rechts
int compareResult; //hier wird das resultat des vergleiches abgespeichert, weil dieser evtl sehr aufwendig sein kann
boolean equalDistributor=false; //das hier wird benutzt, um gleichwertige elemente gleichmäßig nach rechts und links zu verteilen

for(int i=rightSideStart; i<end; i++){
compareResult=array.compareTo(pivot); //vergleichen (evtl. schwierig)
if(compareResult<0 || (compareResult==0 && equalDistributor)){
//entweder ist das element echt kleiner als pivot
//oder es ist gleichwertig, und equalDistributor hat es zufällig nach links geschickt
swap(array,i,rightSideStart); //auf die linke seite verschieben
rightSideStart++; //grenze zwischen links-rechts nach rechts verschieben
equalDistributor=!equalDistributor; //umschalten, damit das nächste gleichwertige nach rechts kommt.
}
}

return rightSideStart; //grenze zwischen links-rechts zurückgeben
}

private <T> void swap(T[] array, int a, int b) {
T temp = array[a];
array[a] = array;
array = temp;
}

//kleiner test
public static void main(String..._){
String[] array={"a","b","A","A","a","ab","bb","a","a","wtf"};
(new Quicksort2()).sort(array);
System.out.println(Arrays.toString(array));
}
}
[/HIGHLIGHT]
Ich habe mir den Spaß erlaubt ein paar methoden umzubenennen, bin beim lesen einfach durchgegangen, hab alles durch für mich weniger gewöhnungsbedürftige und optisch besser unterscheidbare bezeichner ersetzt.

In deinem code fand ich diesen Aufruf "qsort(list,0,length-1)" sehr unschön.
Das bringt absolut gar nichts außer verwirrung und dauernden umindizierungsfehlern. Immer mit dem index 0 und mit dem Index des ersten Elementes nach dem ende des Arrays arbeiten, da erspart man sich eine menge ärger: man braucht da nämlich nirgends <= oder +1 -1.

Was du da mit deinen drei verschachtelten schleifen machen wolltest mag zwar richtig gewesen sein (ich meine sowas mal bei der wikipedia gesehen zu haben, ist wohl ein echt weit verbreiteter ansatz) aber ich finde diese vorgehensweise extrem verwirrend, daher habe ich das bisher immer mit einer schleife erledigt, soll mir doch bitte einer erzählen, was daran schlechter sein soll.

Weil es so lustig war, habe ich nochmal so eine merkwürdige "equalDistributor" variable aufgebaut. Diese sorgt lediglich dafür, dass im Array mit vielen gleichen elementen nicht der Worst-case:
[1,1,1,1,1,1,1,1,1]
[1][1,1,1,1,1,1,1,1]
[1][1][1,1,1,1,1,1,1]
...
eintritt (wo jedes mal nur ein element abgespalten wird)
sondern alles stets auf 2 gleichgroße haufen verteilt wird, also:
[1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1][1,1,1,1,1]
[1,1,1][1,1][1,1,1][1,1]
...
ich hab's zwar jetzt nicht ausführlich getestet, aber es sollte eigentlich klappen.

K.A. hoffentlich hilft's was statt noch mehr zu verwirren

 

[0x7F800000]

Aaaah, okay, hab's mir eben nochmal etwas genauer durchgelesen, bin zum schluss gekommen, dass deine Lösung dann wohl doch etwas effizienter sein müsste.

Moment, ich versuche jetzt nochmal deine variante korrekt hinzufummeln^^

edit: ne! Ich schaue mir jedes element exakt 1 mal an. Weniger geht nicht. Da kann man so viele schleifen drumrumbauen wie man will, aber es ist absolut unmöglich das irgendwie schneller zu bekommen, als ich das mit einer schleife getan habe. Oder ich habe einen extrem krassen denkfehler. :?

 

[gd12]

Ich habe "versucht" diesen Pseudo-Code umzusetzen.

 

[0x7F800000]

nunja... das ist halt so ein Problem, wenn man irgendetwas abtippt, was man sich nicht selbst ausgedacht hat.
Entweder hast du es nicht sorgfältig genug abgetippt, oder derjenige der die aufgabe gestellt hat, hat den pseudocode nicht sorgfältig genug aus einem buch abgeschrieben, oder der autor des buches hat es nicht sorgfältig genug von einem anderen buch abgeschrieben usw usw... Am Ende weiß nur der Hr. Hoare wie das gemeint war^^

Rechne den pseudocode mit bleistift durch, stelle erstmal fest, ob er überhaupt stimmt.
Dann mache dasselbe mit deinem code und dem debugger.