Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » problem quicksort+frage zur laufzeit

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
23.10.2008, 23:31 Uhr
~timstre
Gast


so, ich sitze immer noch an meiner quicksort aufgabe... so sieht das ganze nun aus, hat auch erstma gut funktioniert, bis ich einen vektor der länge 41 haben wollte.. da blieb das ganze (scheinbar in ner endlosschleife) hängen..

Code:


void quicksort1(vector<int>& intvector,int links, int rechts){
   if (links >= rechts) return;
   int anfang = links;
   int t = rechts;
   rechts--;

   while (links < rechts){
      while (intvector[links] < intvector[t] && links < t)
        links++;
      while (intvector[rechts] > intvector[t] && anfang < rechts)
        rechts--;
      if(links < rechts)
         swap(intvector[links], intvector[rechts]);  
   }
   if(intvector[t]<intvector[links])
      swap(intvector[t] , intvector[links]);

           quicksort1(intvector,0,links-1);
              quicksort1(intvector,links+1,t);
}
void quicksort(vector<int>& intvector){
    quicksort1(intvector, 0, intvector.size()-1);
}
int main()
{
    vector<int> i1(40);//Vector für quicksort  
                                                
    srand(time(NULL));    
    
    //i1 wird mit Zufallswerten gefüllt                                          
    for(int i = 0; i < i1.size(); i++){            
        i1[i]=rand() % 100;                    
    }

    cout<<"i1:"; //i1 wird ausgegeben
    for(int i = 0; i < i1.size(); i++)            
        cout << i1[i] <<" ";                    
    cout << endl;
    
    clock_t start, end;
    double time1, time2;
    
    start = clock();
    quicksort(i1);//i1 wird sortiert
    end = clock();
    //time1 wird die Zeit für quicksort zugewiesen
    time1 = (double) (end-start)/CLOCKS_PER_SEC;

    
    cout<<"i1:";//i1 wird sortiert ausgeben;
    for(int i = 0; i < i1.size(); i++)              
       cout << i1[i] <<" ";
    cout<<endl;
    

    cout <<endl<<"time1: "<<time1;
    cout << endl << endl;


    return 0;
}


weiterhin würde mich interessieren, was ihr von der methode, die laufzeit zu bemessen haltet, ist die so in ordnung?.. hatte nämlich auch schon nen zweiten vektor deklariert, der dieselben werte wie i1 bekommen hat, wurde dann aber mit gnomesort sortiert, laufzeitbemessung genauso... dabei kam dann raus das gnomesort schneller ist, was mich sher gewundert hat?? sollte doch andersrum sein oder??
na gut, hoffe mir kann jemand helfen... schönen abend noch
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
24.10.2008, 16:56 Uhr
virtual
Sexiest Bit alive
(Operator)


Unabh von der Frage, ob du nun richtig und effizient implementiert hast,
ist ein test mit grade mal 40 Elementen nicht besonders aussagekräftig.
Ich würde mal mit so 1000 Elementen aufwärts handtieren...

Was den Algorithmus an sich angeht: der ist vermutlich nicht richtig.
Vgl. auch www.hipphampel.de/index.php5?item=cpp/sorting/quicksort
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
25.10.2008, 04:09 Uhr
Pler
Einer von Vielen
(Operator)


Falls Dir das Program time zur Verfügung steht, kannst du damit sehr einfach die Laufzeit eines Programms messen.
Zum Vergleich der Laufzeit kannst Du Dein Programm einfach mit der Laufzeit von sort() aus der STL vergleichen.

http://msdn.microsoft.com/en-us/library/ecdecxh1(VS.71).aspx
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: