Quicksort ArrayOutOfBounds

[Schattenfänger]

Hallo,
Ich wollte QS implementieren, allerdigns bekomme ich immer eine Fehlermeldung wobei mir klar ist was sie bedeuted aber nicht rausfinde wo der Fehler entsteht (ja, bereits durchdebuggt) bzw wo das j plötzlich so hoch gesetzt wird.

  private void swap(int i, int j, int[] data) {
        System.out.println("i: "+i+" j: "+j);
        int x = data[i];
        data[i] = data[j]; //FEHLER
        data[j] = x;
    }

 private void Quicksort(int[] data,int left,int right){

        if(data.length<=1)return;

        int pivot = data[data.length-1];
        int i=left;
        int j=right;

        while(i<=j){
            while(data[i]<pivot){
                i++;
            }
            while(data[j]>pivot){
                j--;
            }
            if(i<=j){
                swap(i,j,data);
                i++;
                j--;
            }
        }
        swap(i,pivot,data);
        Quicksort(data,0,j);
        Quicksort(data,i,data.length);
    }

Wobei ich bei der Ausgabe sehe:. i: 878 j: 893 und danach:
i: 892 j: 1689148175

Habe ich das richtig verstanden, dass nachdem i und j übergeelaufen sind, i mit dem pivot getauscht wird? (Weshalb?)

offtopic: Muss man um Java 8 Streams und Co verwenden zu können irgendwas spezielles in der IDE einstellen? Mein JDK ist 8 und Project Language Level ebenfalls, aber IntelliJ regt sich über Java 8 Befehle auf...

mfg

 

[striker159]

dein swap nimmt als erstes und zweites argument die indizies. aber in zeile 29 übergibst du als 2. parameter das pivotelement selbst, nicht den index zum pivoelement

 

[Schattenfänger]

Danke sehr.

Aber natürlich entsteht ein neues Problem. Ich bekomme einen Stackoverflow.
j zählt schön hinunter auf ~300 und i rauf. Dann nimmt j plötzlich den Wert 999 an und später zieht i damit nach.

Ich glaube, dass ich bei den beiden rekursiven Aufrufen die i und j verwechselt habe, wenn ich diese umtausche bekomm ich wieder einen IndexOutOfBounds...

 

[VikingGe]

Nun, du hast einfach eine endlose Rekursion gebaut.

if (data.length <= 1)
  return;

Heißt: Wenn das Array nur ein Element hat, hörst du auf zu sortieren. Da du aber immer dasselbe Array übergibst...

Quicksort(data,0,j);
Quicksort(data,i,data.length);

...ist die Bedingung entweder von Anfang an wahr oder immer falsch, sodass du keine wirkliche Abbruchbedingung hast. Was du eigentlich willst, ist, die Indizes deines aktuellen Abschnitts - also left und right - miteinander zu vergleichen, denn wie man unschwer erkennt, ändern die sich mit jedem Aufruf.

 

[Schattenfänger]

Sorry, dass ich es nicht erwähnt habe, die Abbruchbedingung habe ich bereits zuvor geändert.
Sie ist jetzt: right-left<=1

 

[Darlis]

Quicksort(data,i,data.length);

Den index data.length gibt es in data nicht -> ArrayOutOfBounds
Warum fängst du nicht mit einem kleinen, überschaubaren Array an, dass sich viel einfacher debuggen lässt?

 

[thecain]

offtopic: Muss man um Java 8 Streams und Co verwenden zu können irgendwas spezielles in der IDE einstellen? Mein JDK ist 8 und Project Language Level ebenfalls, aber IntelliJ regt sich über Java 8 Befehle auf...

mfg

Im "ProjektTree" auf dem Root-Element F4 (Weiss gerade nicht wie der Menupunkt genau heisst) drücken und dann hats einen Listbox welche Javaversion man verwenden will. Standardmässig ist da die Version glaub ich auf Java 7 oder 6. Muss man immer umstellen.

 

[Schattenfänger]

Okay, ich habe es jetzt mal mit einer Größe von 6 durchgebuggt aber ich bekomme trotzdem einen Bufferoverflow und einige hundert Ausgaben.
Allerdings bin ich mal draufgekommen, dass es wohl nicht zu empfehlen ist, dass ich bei jeder Rekursion pivot=data.len-1 annehme und ein paar Indezes hab ich auch geändert.
Mir fällt auf, dass ich teilweise, dass pivot hin und her swappe obwohl ich es nicht bräuchte.
Sprich ich komme von links und wähle ein i aus, und mein j bleibt genau auf dem pivot index stehen, obwohl ich in der Schleife ja eine größer-Relation drin habe..

  private void Quicksort(int[] data,int left,int right){

        if(right-left<=1)return;

        int pivot = data[right];
        int i=left;
        int j=right;

        while(i<j){
            while(data[i]<pivot){
                i++;
            }
            while(data[j]>pivot){
                j--;
            }
            if(i<j){
                swap(i,j,data);
                i++;
                j--;
            }
        }
      swap(i,right,data);
        Quicksort(data,0,i-1);
        Quicksort(data,j+1,data.length-1);
    }

 @Override
    public void useqsort(int[] data) {

        int pivot = data[data.length-1];
        int i=0;
        int j=data.length-1;

        while(i<=j){
            while(data[i]<pivot){
                i++;
            }
            while(data[j]>pivot){
                j--;
            }
            if(i<=j){
                swap(i,j,data);
                i++;
                j--;
            }
        }
        swap(i,data.length-1,data);
        Quicksort(data,0,i-1);
        Quicksort(data,j+1,data.length-1);
    }

Irgendwo komm ich bei den Indezes durcheinander...

 

[Darlis]

Quicksort enthält fast den selben Code wie useqsort, das sieht nicht richtig aus. Außerdem solltest du Methodennamen kleinschreiben, das ist in Java so üblich.
Der Pseudocode auf wikipedia ähnelt deinem Code und wählt das Pivotelement auch vom Index rechts, das j wird dort aber auf rechts-1 gesetzt. Dadurch wird bei dir das Pivotelement verschoben.

 

[Schattenfänger]

Nein, beim pivot ging es mir ja darum, dass ich jedes mal den Wert ganz rechts als Pivot angenommen habe.
Aber ich muss doch bei QS bei jeder Teilliste ein neues Pivot Element auswählen und wenn ich nun immer von len-1 nehme passt das ja nicht.

 

[Darlis]

Du nimmst auch nur ein mal das Pivotelement aus data.length-1 in useqsort, in Quicksort nimmst du es vom Index rechts, das passt also. Zudem bleibt das Pivotelement auch nicht an der selben Stelle sondern wird (fast) immer verschoben. In data.length-1 wird also (fast) immer ein anderes Element stehen.

 

[Schattenfänger]

Ja, das hatte ich in der alten Version ja noch nicht drin

Ich habe jetzt nochmal von 0 wegprogrammiert (was wieder auf einen sehr ähnlichen Code hinausläuft) aber komme schon wieder auf Fehler.
Einmal bekomm ich die korrekte Ausgabe, einmal eine Endlosschleife und einmal eine falsche Ausgabe.

Ich habs auch nochmal aufgezeichnet aber sehe nicht wo der Fehler im Code entsteht.

 

[Darlis]

Wie sieht denn der jetzige Code aus?