4. Problem mit Sortieralgorithmen (speziell Quicksort)

Problem mit Sortieralgorithmen (speziell Quicksort)

  • F

    Hallo,
    ich habe gerade mit C angefangen und arbeite mich durch die Galileotutorials.
    Habe aber ein kleines Problem, wo ich einfach nicht weiterkomme.

    Ich habe 2 INT - Arrays, die mit werten von 1000 absteigend initialisiert werden.
    Diese sollen danach sortiert werden und in eine gemeinsame Datei nach dem Schema "[0-1] [1-2] ..." ausgegeben werden. Bei der sortierten Liste schleicht sich aber dann ein Fehler ein, der die 1000 aus der test_array1 an die Position 0 schreibt.

    [1000-0][0-1][1-2][2-3][3-4][4-5][5-6][6-7][7-8][8-9][9-10][10-11] ....

    Hier der Quellcode:

    /* quicksort.c */
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

/* das Array zum Sortieren */
int test_array1[MAX];
int test_array2[MAX];

void my_qsort(int*, int*);

void init_test_array(int *array) {
   int i, j;
   for(i = MAX,j=0; i >= 0; i--,j++)
      array[j] = i;
} 

void my_qsort(int *links, int *rechts) {
   int *ptr1 = links;
   int *ptr2 = rechts;
   int w, x;

   x = *(links + (rechts - links >> 1));
   do {
      while(*ptr1 < x) ptr1++;
      while(*ptr2 > x) ptr2--;
      if(ptr1 > ptr2)
         break;
      w = *ptr1;
      *ptr1 = *ptr2;
      *ptr2 = w;
   } while(++ptr1 <= --ptr2);
   if(links < ptr2)  my_qsort(links, ptr2);
   if(ptr1 < rechts) my_qsort(ptr1, rechts);
}

int main(void) {
	int i;   
	init_test_array(test_array1);
	init_test_array(test_array2);
  my_qsort(test_array1, test_array1+MAX);
	my_qsort(test_array2, test_array2+MAX); 	  
	freopen("quicksort.txt", "w+", stdout);

   for(i = 0; i < MAX; i++)
      printf("[%d-%d]", test_array1[i], test_array2[i]);
   return EXIT_SUCCESS;
}

    Das ganze ist an das Beispiel 26.4.1 angelehnt von dieser seite:

    http://openbook.galileocomputing.de/c_von_a_bis_z/026_c_paralleles_rechnen_004.htm#mjda1e36529cbd626ff824ba1d3ff0754d

    Ich habe verschiedene Sortieralgorithmen versucht bekomme aber stets dieses Ergebnis als Ausgabe.

    Ich hoffe jemand kann mir hier helfen, bin halb am verzweifeln.

    MfG,

    Fennas

    0
  • G

    Ein Link zum Thema Buecher von Juergen Wolf

    http://www.c-plusplus.net/forum/272350

    0
  • F

    Ok, ich wusste nicht, dass der Herr Wolf hier so im Verruf ist.

    Dann entschuldige ich mich für meine "dumme Frage".

    MfG,
    Fennas

    0
  • G

    Fennas schrieb:

    Ok, ich wusste nicht, dass der Herr Wolf hier so im Verruf ist.

    Dann entschuldige ich mich für meine "dumme Frage".

    MfG,
    Fennas

    Sorry, falls das falsch rueberkam. Die Frage ist bestimmt nicht dumm.
    Vielleicht kann jemand anderes deine Frage beantworten, ich kann mich da
    nicht reindenken.

    Gruesse

    0

  • Fennas schrieb:

    ich habe gerade mit C angefangen

    Gut.

    Fennas schrieb:

    und arbeite mich durch die Galileotutorials.

    Ganz schlecht.
    http://www.c-plusplus.net/forum/272350
    Pfuscher JW hat bei dir also wieder einen gefunden, dem er mit seinem Pfusch auf den Leim geht.

    int i, j;
   for(i = MAX,j=0; i >= 0; i--,j++)
      array[j] = i;

    Dilettantischer Anfängerschrott.
    Führt zu undefiniertem Verhalten, da auf undefinierten Speicher zugegriffen wird.

    i läuft von 1000..0
j läuft von 0..1000

    array[1000] ist aber gar nicht definiert, sondern nur array[0]..array[999].
    Sind alles Grundlagen, man sieht auch hier wieder Pfuscher JW in Reinkultur.

    my_qsort ist auch unsinnig, da qsort schon in der C-Standardbibliothek vorhanden ist, grenzt auch schon an Schizophrenie, das nochmal nachzuimplementieren.

    0
  • F

    Ah ok Danke für den Hinweis und die Hilfe.

    Die eigene Implementierung von qsort ist denke ich dazu gedacht Grundlagen in Sachen Sortieralgorithmen zu vermitteln.

    Wo kann man sich denn besser online schlau machen zum Thema C?

    0
  • Mod

    Fennas schrieb:

    Wo kann man sich denn besser online schlau machen zum Thema C?

    Zum Beispiel in den als wichtig markierten Threads und den FAQs des Forums. Wirklich gute Onlinequellen um C von Grundauf zu lernen kenne ich aber nicht. Tutorials werden meistens von Anfängern geschrieben, die sich für gut halten, echte Experten schreiben gleich ein Buch.

    0

  • Fennas schrieb:

    Die eigene Implementierung von qsort ist denke ich dazu gedacht Grundlagen in Sachen Sortieralgorithmen zu vermitteln.

    Tja, die Qualität dieser vermittelten Grundlagen scheint doch stark zweifelhaft, da Pfuscher JW schon an der Testdatengenerierung scheitert. Seine Implementierungsversuche der eigentlichen Sortieralgorithmen habe ich mir nicht angeschaut, sind aber bei ihm wie gesagt per se zweifelhaft.

    Fennas schrieb:

    Wo kann man sich denn besser online schlau machen zum Thema C?

    Prata: C-Primer Plus 5.Ed.
    Bücher von Prinz/Prinz, auch ältere

    0

  • SeppJ schrieb:

    Tutorials werden meistens von Anfängern geschrieben, die sich für gut halten, echte Experten schreiben gleich ein Buch.

    Wichtige Ergänzung:
    Tutorials werden meistens von Anfängern geschrieben, die sich für gut halten, echte Experten (meistens auch nur solche, die sich für gut halten) schreiben gleich ein Buch.

    0
  • B

    Noch eine Ergänzung zur Ehrenrettung der Tutorialschreiber: Tutorials werden auch von Anfängern geschrieben, die um ihre Defizite wissen, aber glauben, dass sie gerade deshalb die Probleme anderer Anfänger besser verstehen und darauf eingehen können. Das ist leider ein Trugschluss.

    0

  • Deren Enthusiasmus in allen Ehren, aber meist lassen sich diese Herren eben nicht in die Karten schauen, woher ihr präsentiertes Wissen kommt, z.B. sind Hinweise auf den Standard oder zumindest andere kompetente Quellen (z.B. Compiler-Dokumentationen) sehr oft Mangelware.
    Oftmals verweisen sie, wenn sie denn überhaupt verweisen, auf andere Tutorialquellen bzw. beziehen ihr 'Wissen' daraus. Dabei gilt aber: 'Zwei Blinde ergeben noch keinen Sehenden'.
    Wie heißt es doch so schön: 'Er war stets bemüht...'.

    0
Anmelden zum Antworten