quicksort mit array voller zufallszahlen
-
Hallo,
ich habe versucht eine quicksort funktion zu erstellen. Hierzu habe ich mir verschiedene quicksort funktionen angesehen udn versucht sie zu verstehen. Die Aufgabe ist, ein array mit 100 zufallszahlen von 1-1000 sortieren zu lassen.
Nun habe ich folgenden code:
#include <iostream> #include <string> #include <ctime> using std::cout; int partition(int* array, int begin, int end){ int x = array[begin]; /*Pivot*/ int i=begin-1; int j=end+1; int tmp; while(1){ while(array[++i]<x && i<=end); while(array[--j]>x && j>=0); if(i>=j) break; if(array[i]>array[j]){ tmp = array[i]; array[i] = array[j]; array[j] = tmp; } for(; begin < end; begin++) cout << array[begin] ; cout << "\n"; } return j; system("pause"); } void quicksort(int* array, int begin, int end){ int q; if(begin<end){ q = partition(array, begin, end); quicksort(array, begin, q); quicksort(array, q+1, end); } } int main(void){ const int inserts=100; int array[inserts]; int i; for(i=0;i<inserts;++i) // array mit zufallszahlen kleiner als SIZE füllen array[i]=rand()%inserts; for(i=0; i<inserts; i++) cout << array[i]; cout << "\nZum sortieren Taste druecken!"; if(getchar()) quicksort(array, 0, inserts); cout <<"\n"; for(i=0; i<inserts; i++) cout <<array[i]; return 0; }Er wird auch sauber kompiliert tut aber wohl nciht das was er soll
und haut mir am Ende noch einRun-Time Check Failure #2 - Stack around the variable 'array' was corrupted.
raus
-
Hm niemand eine Idee, was ich falsch mach?
-
Lass dir mal ausgeben, auf welche Array-Elemente die partition()-Funktion zugreifen will. Für mich sieht das nämlich nach einem typischen 1-daneben-Fehler aus (sprich: das Array geht von 'array[0]' bis 'array[99]', wenn du da auf das Element 'array[100]' zugreifen willst, bekommst du Probleme.
(und da ist es schon freundlich von deinem Compiler, die Bereichsüberschreitung zu melden)
-
tut mir leid aber ich kriegs net weg? ich dachte das wäre mit +1 erledigt?
-
Hallo,
ThaRealMatix schrieb:
int main(void){ const int inserts=100; int array[inserts]; int i; for(i=0;i<inserts;++i) // array mit zufallszahlen kleiner als SIZE füllen array[i]=rand()%inserts; // Hat nichts mit Deiner Frage zu tun, aber wolltest Du hier nicht Zahlen zwischen 1-1000 ? for(i=0; i<inserts; i++) // Hier machst Du es richtig -> beachte vor allem i< inserts (i=100 wäre ein ungüliger Index) cout << array[i]; cout << "\nZum sortieren Taste druecken!"; if(getchar()) quicksort(array, 0, inserts); // Du rufst quicksort mit inserts=100 auf cout <<"\n"; for(i=0; i<inserts; i++) cout <<array[i]; return 0; }ThaRealMatix schrieb:
Hallo,
int partition(int* array, int begin, int end){ int x = array[begin]; /*Pivot*/ int i=begin-1; int j=end+1; // beim ersten Aufruf ist end=100, j ist jetzt 101 int tmp; while(1){ while(array[++i]<x && i<=end); // Hier steht jetzt i<=end (wenn end=100 ist, läuft i jetzt bis zu dem ungültigen Index 100) // und schlimmer noch ++i ergibt dann den ungültigen Index 101 while(array[--j]>x && j>=0); // --j ist immer noch 100 also auch ein ungültiger IndexIch habe Dir jetzt nur die offensichtliche Indexüberschreitung kommentiert, die beim ersten Aufruf von quicksort entsteht. Sieh Dir nochmal genau an, was Du als begin und end an quicksort und partition übergibst und wie Du sicherstellst, dass Du diesen Bereich nicht überschreitest.
DJohn
Edit: Die Rechtschreibung
-
Hm... also ich habs nun so:
#include <iostream> #include <string> #include <ctime> using std::cout; int partition(int* array, int begin, int end){ int x = array[begin]; /*Pivot*/ int i=begin-1; int j=end; int tmp; while(1){ while(array[i++]<x && i<=end); while(array[--j]>x && j>=0); if(i>=j) break; if(array[i]>array[j]){ tmp = array[i]; array[i] = array[j]; array[j] = tmp; } for(; begin < end; begin++) cout << array[begin] ; cout << "\n"; } return j; system("pause"); } void quicksort(int* array, int begin, int end){ int q; if(begin<end){ q = partition(array, begin, end); quicksort(array, begin, q); quicksort(array, q+1, end); } } int main(void){ const int inserts=100; int array[inserts]; int i; for(i=0;i<inserts;++i) // array mit zufallszahlen kleiner als inserts füllen array[i]=rand()%inserts; for(i=0; i<inserts; i++) cout << array[i]; cout << "\nZum sortieren Taste druecken!"; if(getchar()) quicksort(array-1, 0, inserts); cout <<"\n"; for(i=0; i<inserts; i++) cout <<array[i]; return 0; }und bekomem zumindest keine fehlermeludng mehr, aber die system("pause") wird nicht durchgeführt, die sortierung ist wohl immer noch absolut falsch und ich hab absolut keine ahnung wieso... mit einem "statischen" array hat die noch absolut richtig funktioniert
-
ThaRealMatix schrieb:
aber die system("pause") wird nicht durchgeführt
Dann schau doch mal was unmittelbar vor dem Aufruf von system steht...
-
hm vorher hatte es ja so geklappt.... naja egal
aber wieso funktioniert das sortieren nicht mehr?
-
Hm.. weiss denn keiner Rat? derzeit siehts so aus:
#include <iostream> #include <string> #include <ctime> using std::cout; int partition(int* array, int begin, int end){ int x = array[begin]; /*Pivot*/ int i=begin-1; int j=end; int tmp; while(1){ while(array[i++]<x && i<=end); while(array[--j]>x && j>=0); if(i>=j) break; if(array[i]>array[j]){ tmp = array[i]; array[i] = array[j]; array[j] = tmp; } for(; begin < end; begin++) cout << array[begin] ; cout << "\n"; } return j; } void quicksort(int* array, int begin, int end){ int q; if(begin<end){ q = partition(array, begin, end); quicksort(array, begin, q); quicksort(array, q+1, end); } } int main(void){ const int inserts=100; int array[inserts]; int i; for(i=0;i<inserts;++i) // array mit zufallszahlen kleiner als inserts füllen array[i]=rand()%inserts; for(i=0; i<inserts; i++) cout << array[i]; cout << "\nZum sortieren Taste druecken!"; if(getchar()) quicksort(array-1, 0, inserts); cout <<"\n"; for(i=0; i<inserts; i++) cout <<array[i]; system("pause"); return 0; }
-
ThaRealMatix schrieb:
Hm.. weiss denn keiner Rat?
Wie wäre es denn, wenn du die bisherigen Ratschläge vorher auch mal umsetzt?
CStoll schrieb:
Lass dir mal ausgeben, auf welche Array-Elemente die partition()-Funktion zugreifen will.
Hast du das getan? Was ist dabei rausgekommen?
DJohn schrieb:
Sieh Dir nochmal genau an, was Du als begin und end an quicksort und partition übergibst und wie Du sicherstellst, dass Du diesen Bereich nicht überschreitest.
Hast du das getan? Was ist dabei rausgekommen?
-
ThaRealMatix schrieb:
if(getchar()) quicksort(array-1, 0, inserts);
Willst du das nichtmal korrigieren?