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 |
