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:
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
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