Rekursiver InsertionSort ohne Schleife

[Saggerrr]

Hallo, ich würde gerne eine InsertionSort rekursiv schreiben und komplett auf Schleifen verzichten wollen. Es soll zufällig generierte Arrays sortieren können, welche auch unterschiedlich lang sein können.
Ich versuche mich schon seit einigen Stunden daran und komme einfach nicht weiter.
Dies ist mein Ansatz, doch wenn ich ihn ausführe, taucht "Exception in thread "main" als Fehler auf an der "else if" Stelle. Kann mir einer weiterhelfen?

public static int[] sortR(int[] arr) {
int upto = (arr.length+1)-arr.length;
int current = upto;
if(upto == arr.length)
{
return arr;
}
else if(arr[current] >= arr[current -1])
{
upto++;
}
else {
int tmp = arr[current];
arr[current] = arr[current-1];
arr[current-1] = tmp;
}
return arr;

 

[mrBrown]

Bei welchem arr fliegt denn die Exception?

Und poste doch den ganzen Stacktrace

 

[Saggerrr]

Die Exception fliegt direkt raus. Die Arrays werden gebildet mit
public static void main(String[] args) {
Random rng = new Random();
boolean passed = true;

passed &= test(new int[0]);
{
int[] arr = new int[1];
arr[0] = rng.nextInt(20) - 7;
passed &= test(arr);
}
for(int i = 0; i < 10; ++i) {
int[] arr = new int[rng.nextInt(20)];
for(int j = 0; j < arr.length; ++j) {
arr[j] = rng.nextInt(20) - 7;
}
passed &= test(arr);
}

if(passed) {
System.out.println("All tests passed.");
} else {
System.out.println("Some tests failed!");
}
}
Aber da das eine gegebene Formel war, sollte hier auch nichts dran falsch sein.

 

[mrBrown]

Die Exception fliegt direkt raus.

Ja, aber die Fehlermeldung sollte mehr als nur Exception in thread "main" enthalten.

Aber da das eine gegebene Formel war, sollte hier auch nichts dran falsch sein.

Ist dir aufgefallen, dass dein Code nirgends aufgerufen wird?

Ich versuchs trotzdem mal:

Der erste Test findet mit einem Array der Länge 1 statt, current ist immer 1, also wird in dem Array mit Länge 1 der Wert an Stelle 1 abgefragt, was eine Exception wirft.

 

[Xyz1]

Der Sinn des Unterfangens erschließt sich mir noch nicht:

    public static void main(String[] args) {
        List<Integer> list = // ...
        ssort(list, 0, 0);
        System.out.println(list);
    }

    static void ssort(List<Integer> list, int i, int j) {
        if (j == list.size()) {
            return;
        }
        if (i == 0) {
            list.add(i, list.remove(j));
            i = j++;
        } else if (list.get(i) <= list.get(j)) {
            list.add(i+1, list.remove(j));
            i = j++;
        } else {
            i--;
        }
        ssort(list, i, j);
    }

• optimiert
  
• rekursiv (auch end....)
  
• stabil

hth^^, bis morgen

 

[Saggerrr]

Tut mir Leid, aber aus dem Code werde ich nicht schlau. Trotzdem Danke. Insbesondere weil Eclipse mir List als Fehlerhaft zuweißt und weil die Klassen kein Rückgabearray haben

 

[Xyz1]

import java.util.Arrays;
import java.util.List;

----

Von Arrays hast du nüschts gesagt. Insbesondere weil das Einfügen resp das Aufschieben der Elements dann selber gemacht werden muss, wenn es denn 'full in-place' sein soll.

----

und naja ein Anfänger kann das vielleicht nicht verstehen, anderseits aber hast du gefragt. Du wirst allerdings keine bessere Implementierung deiner Fragestellung finden.

---

Ggf einfach nochmal sagen was du nicht verstehst.

 

[Xyz1]

Doch ein Fehler meinerseits:

    static void ssort(List<Integer> list, int i, int j) {
        if (j == list.size()) {
            return;
        }
        if (i == 0 || list.get(i - 1) <= list.get(j)) {
            list.add(i, list.remove(j));
            i = ++j;
        } else {
            i--;
        }
        ssort(list, i, j);
    }

Das lag aber an das nachträglich eingefügte +1:

            list.add(i+1, list.remove(j));