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;
}