4. Rekursiv

Rekursiv

  • ?

    hallo

    ich habe einen quicksort algorithmus geschrieben
    und er funktioniert.
    Nur gibt es leider bei arrays größer als 10000 elementen
    immer den selben fehler und zwar "0xC00000FD: Stack Overflow"
    und da habe ich mich gefragt ob es daran liegt das der algorithmus
    die maximale rekursions tiefe über schritten hat.

    wo kann ich nun heraus bekommen wie viel ebenen der microsoft visual c++ 6.0 compiler erlaubt?

    vielen dank für eure hilfe(schon mal im vorraus)

    0
  • M

    So allgemein kann man die maximale Tiefe nicht angeben, da das ziemlich von der Anzahl der Parameter der Funktion und den lokalen Variablen in der Funktion abhängt. Allerdings sollte bei 10000 Elementen ein Quicksort noch nicht an die Grenze des Stacks stossen, da du da ja wohl bei einer Rekursionstiefe von ca 14 bist.
    Falls es doch an der Größe des Stacks liegt, müsste bei den Linkereinstellungen eine Möglichkeit sein, die Stackgröße anzugeben.

    0
  • W

    Warum benutzt du nicht qsort, oder war das eine Übung?
    Zeig mal ein wenig Code, dann kann man die Schwachstelle schneller erkennen.

    0
  • ?

    hier ist ein bißchen code
    ich denke der fehler musste wenn in dem abschnitt sein

    int e1=pa-a;
    int e2=(a+n-1)-pd;
    int p1=pb-pa;
    int p2=pd-pc;

    if(e1 > 1)
    {
    int min=min(eA,p1);
    vecswap(a,pb-min,min);
    }
    else _swap(a,pc);
    if(e2 > 0)
    {
    int min=min(eB,p2);
    vecswap(pb,a+n-min,min);
    }

    if(p1 > 1)
    mk_qsort(a,p1,mdepth,depth);
    if( (e1+e2 > 1) && (depth+1 < mdepth) )
    mk_qsort(pb-e1,e1+e2,mdepth,depth+1);
    if(p2 > 1)
    mk_qsort(a+n-p2,p2,mdepth,depth);

    mk_qsort übernimmt 4 parameter(uchar**,int,int,int)

    ich nimm jetzt erstmal einen anderen sortier algorithmus
    danke für die hilfe

    0
  • ?
     

    // siehe http://sattas.homeunix.net/zeugs/quicksort.pdf

#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;

const int MAX = 10000000;
int daten[MAX];

void quicksort( int von, int bis )
{
  int links = von, rechts = bis, mitte, zwischen;
  mitte = ( von + bis ) / 2;
  do{
      for(;daten[links] < daten[mitte]; links++);
          for(;daten[mitte] < daten[rechts]; rechts--);
              if(links <= rechts) 
              { 
                  //Tausch durchfuehren
                  zwischen = daten[links];
                  daten[links] = daten[rechts];
                  daten[rechts] = zwischen;
                  links++;
                  rechts--;
              }
    }
    while (links <= rechts);
    if(von < rechts) quicksort(von, rechts);
    if(links < bis)  quicksort(links, bis);
}

int main()
{
  clock_t t1,t2;
  double ts;
  srand(time(NULL));

  for(int i=0;i<(MAX);i++) 
  {
    daten[i] = rand()%MAX;
  } 

  t1=clock();
  quicksort(0,MAX-1); 
  t2=clock();

  ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
  cout << "\tZeit: " << ts << " QuickSort Test" << endl;
  cout<<endl;       

  getch();
}
    0
Anmelden zum Antworten