4. Fehler in Shell_Sort

Fehler in Shell_Sort

  • S

    Der Shell_Sort stammt aus dem Buch C von A-Z, habe ihn eben nochmals getestet
    und musste feststellen, dass er erst ab dem 2. Element sortiert, habe es nicht
    hinbekommen, es zu korrigieren und hoffe ihr findet den Fehler.
    Der Shell_Sort stammt von der Homepage des Autors (www.pronix.de, aber zZ down),
    es liegt also kein Tippfehler meinerseits vor.

    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;
         }
}

    Er müsste in der letzten Iteration doch eigentlich im 1er Schritt sämtliche
    Elemente vergleichen, aber das erste überspringt er.

    0
  • S

    > for(i=n+1; i<=elemente; i++)

    Ohne das jetzt genau geprueft zu haben: Ich vermute mal, dass es i=n heissen muesste, nicht i=n+1.

    0
  • S

    dacht ich am anfang auch oder i = n-1, aber das ist es nicht

    0

  • 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<= 10

    er kommt für das erste nicht in die schleife rein.
    also bleibt es stehen.

    0
  • S

    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ühren

    So versteh ich das, wenn ich mir das eben nochmal anschaue.

    0

  • debugs doch mal durch, er springt für das erste element nicht in die schleife, und somit bleibt es unberührt.

    0
  • S

    Ich hab keine Ahnung wie man debugt, habe zwar MS VC++ 6 welches nen Debugger hat aber mit umgehen kann ich nicht.

    0
  • P

    wenn du MS VC 6.0 hast, schau mal in die Hilfe
    Stichpunkte Singelstep, debuggen,....

    0
  • S

    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.

    0
  • P

    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

    0
  • S

    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 8

    Da stimmt etwas nicht, deshalb ist der wohl auch so viel schneller fertig,
    war Gestern wohl nur Glück, dass die Reihenfolge stimmte.

    0
  • P

    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
    genutzt

    for(i=0;i<3;i++)
    printf("$i\n",a[i]);

    0
  • S

    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.

    0
  • S

    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?

    0
Anmelden zum Antworten