Algorithmus "insertion sort" in C

[Roland]

Hallo

Vielleicht kann mir hier jemand bei meinem Algorithmus "insertion sort" in C
weiterhelfen.

C-Code:

struct test *sTest

// vector of struct pointers
struct test *pt_test[10];
for (i = 0; i < 10; i++) {
pt_test[i] = sTest;
sTest = sTest->next;
}

// algorithm "insertion-sort"
for (n = 1; n < 10; n++) {
m = n;
while ((m > 0) && ((strcmp((char*) pt_test[m - 1]->cName, (char*)
pt_test[n]->cName) > 0))) {
strcpy((char*)pt_test[m]->cName, (char*)pt_test[m - 1]->cName);
m--;
}
strcpy((char*)pt_test[m]->cName, (char*)pt_test[n]->cName);
}


Der "insertion-sort" Algorithmus macht leider nicht das was er sollte.
Vielleicht kann mir jemand einen Tipp geben

Vielen Dank

[Daniel Krügler]

Am Dienstag, 10. April 2012 19:16:56 UTC+2 schrieb Roland:
> Hallo
>
> Vielleicht kann mir hier jemand bei meinem Algorithmus "insertion sort" in C
> weiterhelfen.

Eigentlich sollte man Fragen, die nach Hausaufgaben aussehen, nicht direkt beantworten. Ist ausserdem nicht wirklich C++, naja.

> C-Code:
>
> struct test *sTest
>
> // vector of struct pointers
> struct test *pt_test[10];
> for (i = 0; i < 10; i++) {
> pt_test[i] = sTest;
> sTest = sTest->next;
> }
>
> // algorithm "insertion-sort"
> for (n = 1; n < 10; n++) {
> m = n;
> while ((m > 0) && ((strcmp((char*) pt_test[m - 1]->cName, (char*)
> pt_test[n]->cName) > 0))) {
> strcpy((char*)pt_test[m]->cName, (char*)pt_test[m - 1]->cName);
> m--;
> }
> strcpy((char*)pt_test[m]->cName, (char*)pt_test[n]->cName);
> }
>
>
> Der "insertion-sort" Algorithmus macht leider nicht das was er sollte.
> Vielleicht kann mir jemand einen Tipp geben

In deiner inneren Schleife greifst du fälschlicherweise auf
pt_test[n]->cName zu. Anstelle dessen musst du dir vor Beginn
der inneren Schleife pt_test[n]->cName in einen Ziwschenpuffer
kopieren und in der Schleife immer darauf zurückgreifen, da
pt_test[n]->cName ja überschrieben wird. Am Ende der Schleife
dann aus dem Puffer wieder nach pt_test[m]->cName kopieren.

Wenn du dir Insertionsort anguckst, wirst du feststellen, dass
der Speicher für ein zu sortierendes Element erforderlich ist,
gelle?

Besten Gruss aus Bremen,

Daniel Krügler