Wo liegt der Fehler? Fehler in vier Zeilen…

[nachti74]

Moin zusammen,
hänge leider an dieser Altklausur Aufgabe und wäre froh, wenn mir jemand hilft. Wo sind die Fehler in den 4 Zeilen?
Klammer, Semikolon oder Syntax braucht man nicht suchen, da der Fehler auf semantischer Ebene ist.
Meine Vermutung wäre: Zeile: 1, 8, 15 & 16.

void radixsort(int *a, int n, int d){
int i, j, m, p=1, index, temp, count = 0;
list<int> buckets[10];
for(i=0; i<d; i++){
m=pow(10,i+1);
p= pow(10,i);
for(j=0;j<n;j++){
temp= a[j]%m;
index = temp - p;
buckets[index].push_back(j);
}
count=0;
for( j=0; j<=10; j++){
while (!buckets[j].empty()){
a[count]= *(buckets[j].begin());
buckets[j].erase(buckets[j].begin());
}count++;
}
}
}

[nachti74]

@nachti74 Übrigens soll das ein Quelltext für das Sortiralgorithnus RadixSort sein.

[Swordfish]

Warum sortiert man Daten die nativ binär vorliegen krampfhaft im Zehnersystem?

[nachti74]

@Swordfish das weiß ich nicht. Das ist eine Altklausuraufgabe. Weißt du denn wo die Fehler sind?

[It0101]

Was soll denn das Programm tun? Vielleicht kannst du das kurz beschreiben.
Schön wäre auch noch, wenn es unter zuhilfenahme der "CodeBlocks" hier formatiert wäre, damit es besser lesbar ist.

[nachti74]

@It0101 das Programm ist ein Sortieralgorithmus des RadixSorts.

[It0101]

@nachti74 sagte in Wo liegt der Fehler? Fehler in vier Zeilen…:

@It0101 das Programm ist ein Sortieralgorithmus des RadixSorts.

Ich meinte eher die Funktionsweise der einzelnen Zeilen. Den Fehler kannst du nur dann finden, wenn du den Algorithmus, bzw. die Zeilen komplett verstanden hast.

[nachti74]

@It0101 ja soweit alles verstanden. Trotzdem komme ich nicht auf die Fehler.

[Belli]

@nachti74 sagte in Wo liegt der Fehler? Fehler in vier Zeilen…:

Moin zusammen,
hänge leider an dieser Altklausur Aufgabe und wäre froh, wenn mir jemand hilft. Wo sind die Fehler in den 4 Zeilen?
Klammer, Semikolon oder Syntax braucht man nicht suchen, da der Fehler auf semantischer Ebene ist.
Meine Vermutung wäre: Zeile: 1, 8, 15 & 16.

void radixsort(int *a, int n, int d){

Was ist denn Deine Vermutung, was in Zeile 1 falsch ist?

[nachti74]

@Belli würde sagen der Funktionsaufruf, da fehlt was.

[DirkB]

@nachti74 sagte in Wo liegt der Fehler? Fehler in vier Zeilen…:

@Belli würde sagen der Funktionsaufruf, da fehlt was.

Der fehlt komplett, da du „nur“ die Definition der Funktion gezeigt hast.

[Belli]

@nachti74 sagte in Wo liegt der Fehler? Fehler in vier Zeilen…:

@Belli würde sagen der Funktionsaufruf, da fehlt was.

Ich sehe da (in Zeile 1) gar keinen Funktionsaufruf ...

[nachti74]

@Belli also wäre da kein Fehler?

[nachti74]

Wäre super, wenn mir jemand die Fehler benennen würde.
Schreibe gleich eine Klausur und wäre vorher super zu wissen, wo die Fehler hier wäre.
Lieben Dank

[nachti74]

@Belli *(buckets[j].begin());

Sollte es nicht *(buckets.begin()) sein?

[Schlangenmensch]

Was soll denn in der Funktionssignatur was sein? (Das sieht wieder sehr nach C im C++ Deckmantel aus...(abgesehen von vermutlich std::list)

Ich würde vermuten: int *a Pointer auf das erste Element eine C Style int arrays. int n vlt die Anzahl an Elementen in dem Array? Was ist dann int d? Soll das die Basis sein? Dann wäre list<int> buckets[10]; falsch.

@nachti74 sagte in Wo liegt der Fehler? Fehler in vier Zeilen…:

Wäre super, wenn mir jemand die Fehler benennen würde.
Schreibe gleich eine Klausur und wäre vorher super zu wissen, wo die Fehler hier wäre.
Lieben Dank

Wie wäre es, wenn du dann erstmal schnell deinen ersten Beitrag editierst und Code Tags um deinen Code machst.
Wodran machst du fest, dass das falsch ist? (Was ist deine Testeingabe, was dein Erwartetes Ergebnis und was bekommst du raus).
Wäre schön, wenn du dein komplettes Beispiel posten könntest, dann könnte man das schnell ausprobieren.

P.S. Die deutsche Wikipedia hat sogar einen ganz brauchbaren C++ Algo für Radix Sort (https://de.wikipedia.org/wiki/Radixsort)

[nachti74]

@Schlangenmensch erstmal danke für den Beitrag, das hilft mir sehr. Beim radix Sort wird sonsotiert, dass wir z.B 7 Eimer (Buckets) haben und pro Eimer z.b die Zahlen (012),(203),(003),(074,(024),(017),(112).

Im Schritt 1 werden die Eimer nach der Reihenfolge der letzten Ziffern also Position 0 sortiert. Also:
(012),(112) - (203),(003)- (074),(024) - (017)

Im schritt 2 werden die wieder ausgegeben:
(012)(112)(203)(003)(074)(024)(017)

In Schritt 3 werden die Eimer nach der Reihenfolge der mittleren Ziffern also Position 1 sortiert:
Also:
(203)(003) - (012)(112)(017) - (024) - (074)

Schritt 4 wird wieder ausgegeben:
(203)(003)(012)(112)(017)(024)(074)

Schritt 5 werden die Eimer nach der Reihenfolge der ersten Ziffer also Position 2 sortiert. Also:
(003)(012)(017)(024)(074) - (112) - (203)

Schritt 6 Endergbenis Ausgabeliste:
(003)(012)(017)(024)(073)(112)(203)

[nachti74]

@Schlangenmensch habe noch folgendes gefunden:
sequence<Elem> ksort(sequence<Elem> s) {

b = new Sequence <Elem> [k];

foreach ( e ∈ s)
b[key(e)].pushBack(e);
Return concatenate (b); // Aneinanderreihung von b[0],..b[k-1]

[nachti74]

@nachti74

radixSort (Sequence <Elem> s){
for(int i=0; i<d; i++)
kSort (s,i); // sortiere gemäß key(x)
// mit key(x) = (key(x)/k^i) mod k

[DirkB]

@Schlangenmensch sagte in Wo liegt der Fehler? Fehler in vier Zeilen…:

Was ist dann int d? Soll das die Basis sein?

Das sieht eher nach der Anzahl der Stellen aus.
(daraus wird ja mit pow die Wertigkeit der Stellen berechnet)