Fehler in Shell_Sort
-
dacht ich am anfang auch oder i = n-1, aber das ist es nicht
-
das ist aber die richtige stelle
for(i=n+1; i<=elemente; i++)
er überspringt dir doch die schleife für das erste element, weil du da stehen hast:
i=11
und i<= 10er kommt für das erste nicht in die schleife rein.
also bleibt es stehen.
-
n ist aber nicht die Anzahl der Elemente, Beispiel:
10 Elemente und Distanz 2:
n = 10/2 // n = 5
i = n+1 // Weil Nachkommastellen wegfallen und somit ein Element doppelt vorkäme?
// so lange i kleiner oder gleich 10 ist die innere Schleife ausführenSo versteh ich das, wenn ich mir das eben nochmal anschaue.
-
debugs doch mal durch, er springt für das erste element nicht in die schleife, und somit bleibt es unberührt.
-
Ich hab keine Ahnung wie man debugt, habe zwar MS VC++ 6 welches nen Debugger hat aber mit umgehen kann ich nicht.
-
wenn du MS VC 6.0 hast, schau mal in die Hilfe
Stichpunkte Singelstep, debuggen,....
-
Habe die deutsche version wie heißt das da?
Singlestep findet er nicht und habe bei all den Themen auch nix gefunden was für
Zeilenweise ausführen stehen könnte.
-
Single einzel
Step schritt
=> Einzelschritt (StepInto)
/* debugger */ in den Code schreiben cursor auf das debugger und F1 drücken
dann die Punkte Visual C++ Benueter Führer (user´s guide) durchlesen
Oder im Baum-Diagramm den Punkt Visual C++ Documentation -> Using Visual C -> Visual C++ User´s Guide -> Debugger anschauen (ich meine nicht den Baum sondern die jeweils dazugehörigen Texte
-
Mit dem Debuggen kam ich nicht wirklich zurecht bzw. ich konnte zwar das ganze so
starten, aber es nütze mir nichts
Ich habe nun noch einen 2. Shell-Sort gefunden, der zwar um das 10fache langsamer
ist, aber auch er überspringt die ersten Elemente, kann es an der Initialisierung
liegen?Hiermit wird das Array initialisiert:
void init_test_array() { int i,j; for(i=MAX,j=0; i>=0; i--,j++) test_array[j]=i; }Edit:
Irgendwie stimmt das überhaupt nicht so ganz, hier mal das Programm von Pronix.de:
#include <stdio.h> #include <time.h> #define MAX 10000000 #define MAX_TEST 10 /*Das Array zum Sortieren*/ int test_array[MAX]; void init_test_array() { int i,j; for(i=MAX,j=0; i>=0; i--,j++) test_array[j]=i; } void shellsort(int array[], int elemente, int distanz) { int i,j,temp,n; n=elemente; for(; n>0; n/=distanz){ for(i=n+1; i<=elemente; i++) { temp=array[i]; for(j=i; j>n && array[j-n]>temp; j-=n) array[j]=array[j-n]; array[j]=temp; } } } int main() { int distanz_folge; float zeit; clock_t start, ende; for(distanz_folge=2;distanz_folge <= MAX_TEST;distanz_folge++) { init_test_array(); start = clock(); shellsort(test_array, MAX-1, distanz_folge); ende = clock(); /*Ergebnis der Laufzeitmessung in Sekunden*/ zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC; printf("Die Laufzeitmessung der " "Distanzfolge %d ergab %2.2f Sekunden\n" ,distanz_folge,zeit); printf ("%d %d %d\n",test_array[0],test_array[1],test_array[2]); } getchar (); return 0; }Die Ausgabe:
Die Laufzeitmessung der Distanzfolge 2 ergab 2.61 Sekunden
10000000 1 2
Die Laufzeitmessung der Distanzfolge 3 ergab 1.91 Sekunden
10000000 1 2
Die Laufzeitmessung der Distanzfolge 4 ergab 1.80 Sekunden
10000000 1 2
Die Laufzeitmessung der Distanzfolge 5 ergab 1.78 Sekunden
10000000 1 2
Die Laufzeitmessung der Distanzfolge 6 ergab 1.86 Sekunden
10000000 3 2
Die Laufzeitmessung der Distanzfolge 7 ergab 2.06 Sekunden
10000000 1 2
Die Laufzeitmessung der Distanzfolge 8 ergab 2.02 Sekunden
10000000 3 2
Die Laufzeitmessung der Distanzfolge 9 ergab 2.11 Sekunden
10000000 1 2
Die Laufzeitmessung der Distanzfolge 10 ergab 2.00 Sekunden
10000000 9 8Da stimmt etwas nicht, deshalb ist der wohl auch so viel schneller fertig,
war Gestern wohl nur Glück, dass die Reihenfolge stimmte.
-
An der Stelle kann man nur sagen kümmere dich ums debuggen, schau die die Inhalte der Variabeln an während du mit StepInto (Singelstep) durch das Programm gehst. Routinen aus der C/C++ Library solltest su mit StepOver überspringen.
Nimm zum anfang einfach ein Feld mit 3 unsortierten Elementen und sortiere diese und schaue die Schritt für Schritt an was passiert.
Wenn du zwei Shell Sort findest und beide sortieren bei dir erst ab dem element a[1] und nicht a[0] könnte es eher an dir und deiner Initialisierung liegen als an den Sort Verfahren.
Eine "dumme" Bemerkung: Du weist das in C alle Arrays mit dem Element a[0] anfangen, d.h.
int a[3]; hat die Elemente a[0], a[1], a[2] und das wird in Schleifenoperationen meistens so
genutztfor(i=0;i<3;i++)
printf("$i\n",a[i]);
-
Das Probem ist, eine einfachere version von diesem Shellsort auch von pronix.de
sortiert auch nicht richtig, er vertauscht die 0 und die 1.
Aber durch deinen letzten Tipp, könnt ich mal was versuchen.Edit:
Ne liegt nicht daran, dass er i prüft und nicht j, mal das mitm kleinen Array testen.Edit:
Ich glaub ich schlaf mal ne Nacht drüber und lies mal das Kapitel zu Shellsort
in Algorithmen in C durch und versuch mal meinen eigenen zu implementieren.
Vllt. find ich dann ja den Fehler darin.
-
Diese Variante funktioniert:
void shellsort (int a[], int N) { int i, j, h, v; for (h = 1; h <= N/9; h = 3*h+1) ; for (; h > 0; h /= 3) for (i = h+1; i <= N; i++) { v = a[i]; j = i; while (j >= h && a[j-h] > v) { a[j] = a[j-h]; j -= h; } a[j] = v; } }Aber nicht in dem Beispiel oben, da liegt wohl irgendwo nen Fehler vor, in meinem eigenen Testprogramm geht es:
#include <stdio.h> void shellsort (int a[], int N); int main (void) { register int i,j,g; int a[1000]; for (i = 0,g = 999; i < 1000; i++,g--) a[i] = g; int n = sizeof(a)/sizeof(int); shellsort (a, n); for (i = 0; i < 25; i++) printf ("Element%d => %d\n",i,a[i]); getchar (); return 0; }Ich schaffe es aber nicht, die Distanz vorzugeben, experimentiere seit einer
Stunde
Möchte doch nur, dass ich z.B. 9 angebe und er dann immer verkleinert bis es
am Schluss 1 ist.
Wieso rechnet Sedgewick das h überhaupt so komplex aus in ner Schleife die gar
nix tut?
