Thread: Excessive long time on quicksorting

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

> temp = Vector[i];
> Vector[i] = Vector[j];
> Vector[j] = temp;
The size of your struct (approx 16 bytes) probably means the compiler is generating calls to memcpy() to perform your struct assignments.

Calls to memcpy() for small amounts of memory are expensive in relation to the amount of useful work done.

Profile how many times you actually hit these 3 lines.

It steps 341125075 times (for a 10000 long array) through those 3 lines - this is way past O(n log n) complexity.

Times that large for such a small struct to me make it jump out right away that it cannot simply be inefficiency of individual operations.
Plugging this code directly into my sorting algorithm demo program indicated that it is far worse than O(n*n) running time, and in fact looks somewhat similar in operation to Stooge Sort!
There was clearly some serious algorithmic flaw here in this implementation.

It turns out that the problem is that the recursive calls are being made from inside the loop. These calls need tobe made after the while loop. Fixing that makes it run as expected. So you only had one bracket in the wrong place.

No, there is no need to define a custom assignment operator.