Slowsort in java

[bRainLaG]

Hi ich muss den Slowsort Algorithmus umsetzen, und bekomme dabei einen Fehler, den ich irgendwie nicht vermeiden kann.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sortalgo;

import java.util.Arrays;
import java.util.Random;

/**
 *
 * @author ich
 */
public class SlowSort {

    private int[] num;
    private int numb;

    public void sort(int[] values) {
        if (values == null || values.length == 0) {
            return;
        }

        this.num = values;
        numb = values.length;
        slowsort(values,0, numb-1);
    }

    private void slowsort(int[] values, int i, int j) {
        if (values[i] >= values[j]) {
            int m = (i + j) / 2;
            slowsort(values, i, m);
            slowsort(values, m + 1, j);
            if (values[j] < values[m]) {
                int temp = num[j];
                num[j] = num[m];
                num[m] = temp;
                }
        }
        slowsort(values, i, j - 1);
        
    }

    public void random(int[] array) {

        for (int k = 0; k < array.length; k++) {
            Random r = new Random();
            int rand = r.nextInt();
            array[k] = rand;

        }
    }

    public static void main(String[] args) {

        int [] values;
        values = new int [3];

        SlowSort slow = new SlowSort();
        slow.random(values);
        slow.sort(values);
        System.out.println(Arrays.toString(values));

    }
}

Exception in thread "main" java.lang.StackOverflowError
        at sortalgo.SlowSort.slowsort(SlowSort.java:30)
        at sortalgo.SlowSort.slowsort(SlowSort.java:32)
        at sortalgo.SlowSort.slowsort(SlowSort.java:32)
        at sortalgo.SlowSort.slowsort(SlowSort.java:32)
        at sortalgo.SlowSort.slowsort(SlowSort.java:32)

Ich hab mich an den Pseudocode gehalten, den es auf Wikipedia gibt, und habe den Algorithmus auch durchgespielt, ich komme trotzdem nicht drauf, warum ich den StackOverflow bekomme. Ich hoffe es hat jemand einen Tipp

 

[Marco13]

private void slowsort(int[] values, int i, int j) {
    System.out.println("Aufruf mit "+i+" und "+j+" auf einem array mit "+array.length+" elementen");
...

 

[bRainLaG]

Ahhh ok der Tipp ist ganz gut, hab dabei festgestellt, das j nicht mit numb-1 initialisiert wird, wie es sein sollte, sondern mit mit j = 0 nur hab ich die initialisierung in der Sort Methode nun auch mit values.length -1 getestet aber er nimmt trotzdem 0 ich seh den Fehler nicht ganz

 

[SlaterB]

bisschen spät, aber bevor ich alles lösche:

was verstehst du unter 'drauf kommen', wie gehst du vor?
starrst du die ganze Zeit auf den Code und wartest auf eine göttliche Eingebung?

man kann in solchen Fällen immer methodisch strukturiert vorgehen,
- verzichte auf Random, setze 3 bestimmte Werte
- du solltest natürlich in etwa wissen, worum es in dem Programm geht, das ganze auf Papier durchrechnen können
-> daraus wird klar ersichtlich, dass die Methode slowsort() maximal 1-3x rekursiv ineinander aufgerufen wird,
wenn es bei dir 10x bzw. 1000x passiert, liegt wohl ein Fehler vor
-> schon ist der Fehler ganz klar eingegrenzt, bzw. ergibt sich quasi aus der Fehlermeldung: die slowsort()-Aufrufe sind komisch, WARUM sind sie so?
- nun der entscheidende Schritt, eigentlich banal, aber man muss es wohl sagen: schaue dir an, warum das so ist!,
gib zu Beginn der slowsort-Methode bzw. vor dem rekursiven Aufruf die Indexe aus, mit denen die Methode aufgerufen wird,
schaue dir an welche Indexe, besonders ob es eine Schleife mit immer wieder denselben Indexen gibt, der Standardfehler,
vergleiche das mit deiner manuellen Rechnung, wo stimmt es nicht überein, finde dann den Grund,
falsche Indexberechnung, falsche Behandlung eines Spezialfalls usw.


ganz simple Schritte, ist das wirklich schwer? kann dazu nur die Alternative sein 'ich verstehe es nicht'?
na gut, mag bei Anfängern ja immer so sein, hoffentlich habe ich einen weiteren bekehrt, mit strukturellen Denken zu beginnen

-----

etwas genauer:
die Indexe sind alle 0, rekursiv wird immer 0,0 aufgerufen, m ist davon 0, wieder 0,0 usw.,
da musst du abbrechen, so schwer zu sehen? ruhig auch 5 Min. vor einer nächsten Antwort nachdenken

 

[bRainLaG]

Ja ich habs in dem Moment auch gesehen, das mir die Abbruch Bedingung fehlt, er nämlich dann einfach immer weiter macht. hab erst gedacht ich hab im Aufruf einen Fehler also an der falschen Stelle geschaut. Hab anfangs geglaubt der Fehler liegt beim Aufruf, war also meine Schusseligkeit

Vielen dank trotzdem Slater ich werde das für die nächsten Programme mitnehmen

Und zum Abschluss das ganze nochmal funktionierend:
(Vielen Dank euch beiden und viel Spaß den Leuten die es auch brauchen )

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sortalgo;

import java.util.Arrays;
import java.util.Random;

/**
 *
 * @author ich
 */
public class SlowSort {

    private int[] num;
    private int numb;

    public void sort(int[] values) {
        if (values == null || values.length == 0) {
            return;
        }
        this.num = values;
        numb = values.length;
        slowsort(values,0, numb - 1);
    }

    private void slowsort(int[] values, int i, int j) {
        if (values[i] == values[j]){
            return;
        }
        if (values[i] >= values[j]) {
            int m = (i + j) / 2;
            slowsort(values, i, m);
            slowsort(values, m + 1, j);
            if (values[j] < values[m]) {
                int temp = num[j];
                num[j] = num[m];
                num[m] = temp;
                }
        }
        slowsort(values, i, j - 1);
        
    }

    public void random(int[] array) {

        for (int k = 0; k < array.length; k++) {
            Random r = new Random();
            int rand = r.nextInt();
            array[k] = rand;

        }
    }

    public static void main(String[] args) {

        int [] values;
        values = new int [5];

        SlowSort slow = new SlowSort();
        slow.random(values);
        slow.sort(values);
        System.out.print(Arrays.toString(values));

    }
}