I'm using Kruskal's algorithm for minimal cost tree to solve a high school c++ problem.

The graph is represented in an array of arcs. My problem is rather odd: quicksort takes an awful lot of time (17 sec on an AMD Athlon LE-1640 2.59Ghz) sorting the array by its .c member value. What's wrong with my code?

The values i'm testing for are: N(number of nods in the graph) = 500, M(number of arcs in the graph) = 10000.

LE: Solved - The quicksort algorithm's implementation was wrong - the recursive calls should be made outside the while loop.

Code:#include <fstream> using namespace std; ifstream i_file("retea.in"); ofstream o_file("retea.out"); #define Nmax 1001 #define Mmax 20001 #define Kmax 50001 struct Conexiune { int x; int y; double c; }; void Quicksort(int left, int right, Conexiune Vector[]) //<--takes 17 sec to sort the array { int i = left; int j = right; Conexiune temp; Conexiune pivot = Vector[(i+j)/2]; while(i<=j) { while(Vector[i].c<pivot.c) i++; while(Vector[j].c>pivot.c) j--; if(i<=j) { temp = Vector[i]; Vector[i] = Vector[j]; Vector[j] = temp; i++; j--; } } //<---Fixed bracket :) if(left < j) { Quicksort(left,j, Vector); } if(i<right) { Quicksort(i, right, Vector); } } Conexiune Muchie[Mmax]; int N, M, K; int Familie[Nmax]; int Selectat[Mmax]; int main() { int i, j; i_file>>N>>M>>K; for(i=0; i<M; i++) { i_file>>Muchie[i].x>>Muchie[i].y>>Muchie[i].c; if(i<N) { Familie[i+1] = i+1; } Selectat[i]= 0; } Quicksort(0, M-1,(Conexiune*) Muchie); i=N-1; while(i>0) { for(j=0; j<M; j++) { if(Familie[Muchie[j].x]!=Familie[Muchie[j].y]) { int min, max; Selectat[j] = 1; if(Familie[Muchie[j].x] < Familie[Muchie[j].y]) { min = Familie[Muchie[j].x]; max = Familie[Muchie[j].y]; } else { max = Familie[Muchie[j].x]; min = Familie[Muchie[j].y]; } for(int z = 1; z<=N; z++) { if(Familie[z] == max) { Familie[z]= min; } } i--; if(i<0) break; } } } double suma=0; double Vector[Kmax]; int counter = 1; int localcounter = 0; Vector[0] = 0; double max =0; for(i=0; i<M; i++) { if(Selectat[i] == 1) suma = suma + Muchie[i].c; if(Selectat[i] == 1 && max < K) { localcounter =0; for(j=0; j<counter; j++) { if(Muchie[i].c + Vector[j] > max ) { max = Muchie[i].c + Vector[j]; Vector[localcounter+counter] = Muchie[i].c + Vector[j]; localcounter++; } } counter = counter + localcounter; } } o_file<<suma<<"\n"<<counter; return 0; }