Tail-Rekursiver Counting Sort

Cromewell

Top Contributor
Hallo zusammen,

ich versuche gerade einen tail-rekursiven counting sort zu implementieren (in O(n+k), wenn das input array Länge n und k die Länge vom "Zählarray" sind). Dabei soll nur ein Array a (mit den input Werten) und ein Arrays b (Zählarray) übergeben werden. Ich hätte jetzt spontan sowas geschrieben:
Java:
public static int[] csort(int[] a, int[] b){

    int x = a[0];
    b[x]++;

    if(a.length == 1){
        return b;
    } else {
        int[] c = Arrays.copyOfRange(a, 1, a.length);
        return csort(c,b);
    }
}

Aber durch Arrays.copyOfRange() (liegt in O(n)) sind wir ja nicht mehr in O(n+k), soweit ich das sehe... Habt ihr Tipps?

Schönen Abend noch

Cromewell
 

Robert Zenz

Top Contributor
Entschuldige bitte, ich habe keine Antwort auf deine Frage, aber ich moechte dich bitten dass du dir angewoehnst richtige Variablennamen zu verwenden. Wenn du Dokumentation oder Kommentare im Sinne von "Array a (mit den input Werten)" schreiben musst, hast du was falsch gemacht bei den Variablennamen. Es spricht nichts, so richtig gar nichts, dagegen "inputArray" und "zaehlerArray" als Variablennamen zu verwenden. Selbiges gilt natuerlich fuer "x" und "c". Idealerweise kann man jede Zeile Code auch ohne Kontext einigermaszen verstehen, fuer "int x = a[0]" ist das nicht so richtig gegeben. Es macht Code einfach um ein so vielfaches lesbarer und wartbarer wenn man wirklich gute Namen verwendet.
 

Cromewell

Top Contributor
Vielleicht habe ich aber auch die Aufgabenstellung zu genau genommen und man darf andere Parameter hinzufügen. Dann wäre die Aufgabe nämlich einfach...🤔

P.S.: Als weitere Entschuldigung für meine Variablen-Benennung möchte ich noch vorbringen, dass ich aus der Mathematik komme ;p
 
K

kneitzel

Gast
Ja, weitere Parameter (einer, die aktuelle Position, die gezählt wird) sind hier wohl angebracht. Dann kannst Du den aktuellen Wert mit übergeben.

Wenn Du mit dem zählen durch bist: Aus zähl-Array ein Ziel-Array schreiben und zurück geben.
sonst: aktuelles Element "zählen" und dann Ergebnis des Rekursiven Aufrufes mit erhöhter Position.

Das wäre dann eine Tail Rekursion des counting sort Algorithmus.
 

Cromewell

Top Contributor
Genau :) Das wäre dann meine Lösung gewesen:

Java:
public static int[] csort(int[] a, int[] b, int i){

    if(i == a.length){
        return b;
    } else {
        int x = a[i];
        b[x]++;
        return csort(a,b, i+1);
    }
}
Anfangs wird entsprechend mit i=0 aufgreufen.
 
K

kneitzel

Gast
Aber soll nicht ein sortierten Array zurück gegeben werden? Das ist ja nur das zähl-array, das du zurück gibst.

Da fehlt also aus meiner Sicht noch etwas.
 

Cromewell

Top Contributor
Du hast Recht, es ist nicht der vollständige Counting-Sort. Wir sollten zunächst das Zählarray füllen (obige Lösung) und anschließend in Haskell eine Funktion implementieren, die ein solches Zählarray sortiert ausgibt. Das habe ich hier stillschweigend für mich behalten. Es ging also nur um das füllen des Zählarrays :)
 

lara99

Mitglied
Da es hier arg an der ein oder anderen Stelle harkt, hier ist Countig Sort tailrecursive:

Code:
import java.util.Arrays;

public class Test1 {
    public static void tailRecursiveCountingSort(int[] a, int[] cs, int i) {
        if (i >= a.length) {
            int k = 0;
            for (int j = 0; j < cs.length; j++) {
                while (cs[j] > 0) {
                    a[k++] = j;
                    cs[j]--;
                }
            }
            return;
        }
        cs[a[i]]++;
        tailRecursiveCountingSort(a, cs, i + 1);
    }

    public static void main(String[] args) {
        int[] a = { 8, 4, 7, 5, 1, 1, 1, 6, 3, 2, 1 };
        tailRecursiveCountingSort(a, new int[100], 0);
        System.out.println(Arrays.toString(a));
    }
}
 

fhoffmann

Top Contributor
hier ist Countig Sort tailrecursive
Dazu zwei Bemerkungen:

Es ist in diesem Thread schon einmal erwähnt worden, dass vernünftige Variablennamen den Code erst lesbar machen. Mit deinen Variablennamen "a", "i", "j", "k", "cs" etc ist der Code nicht wirklich lesbar (auch wenn er funktioniert).

Wir sollten zunächst das Zählarray füllen
Ich finde die Idee schön, in einer Methode das Zählarray zu füllen und erst dann in einer weiteren Methode wirklich zu sortieren. Eine Aufteilung in zwei (private) Methoden würde deinen Code lesbarer machen.

Aber ansonsten funktioniert dein Code natürlich (solange keine der Zahlen in a nicht kleiner als 0 oder größer als 100 ist).
Aber außer der "Funktionalität" finde ich "Lesbarkeit" auch wichtig.
 
Zuletzt bearbeitet:

Cromewell

Top Contributor
Da es hier arg an der ein oder anderen Stelle harkt
Also eigentlich ist alles klar xD Die Frage anfangs bezog sich darauf, wie man nur mittels der zwei Array-Parameter eine Prozedur schreiben kann, die das Zählarray füllt und die in O(n) liegt. Ist diese Restriktion bzgl. der Parameter nicht gegeben, dann ist die Implementation ja eig. straight-forward.

Dennoch möchte ich allen für die rege Anteilnahme danken :')
 
K

kneitzel

Gast
Sprechende Methodenbezeichner sind wichtig, der Bezeichner lokaler Methodenvariablen ist unwichtig. Von daher ist der Code von lara99 mehr als richtig.
Kannst Du diese Position etwas erläutern? Wie kommt man zu so einer Position?

Das so schlechte Variablennamen Code schlechter lesbar machen ist doch mehr als offensichtlich, daher bin ich jetzt doch etwas verwirrt. Aber das wirst Du ja bestimmt noch etwas begründen können.

(Oder sollte ich auf einen neuen Account von Tobias herein gefallen sein und er bestätigt sich gerade einfach selbst?)
 
K

kneitzel

Gast
Dann schau Dir einfach einmal an, wie da die Parameter benannt sind. Vielleicht kommt dann auch bei Dir etwas Einsicht...
 

Ähnliche Java Themen

Neue Themen


Oben