Shell Sort with Vectors Problem

**TheSpoiledMilk** · 11-17-2005

I have a program that compares the # of moves # of compares and the total time it take to sort a vector of words. The vector has thousands of words to make the sorts take allot of time to make the efficiency of Shell vs Bubble apparent.
The shell sort i have below sorts correctly but it takes way longer then any of the other sorts which i know is wrong. Can someone show me what i did wrong i cannot find it for the life of me.

Code:

//the struct
struct Wrd {
	int wordCounter;				//# of times the word appears
	string theword;                                  //the acutal word
};
//the sort
void shellSort(vector<Wrd>& V, int start, int stop){
   int flag = 1;
   Wrd temp;

     while( flag || (stop > 1)){
         flag = 0;
         stop = (stop + 1) / 2;
         for (start = 0; start < (V.size() - stop); start++){
              if (compare(V[start + stop], V[start])){
                  temp = V[start + stop]; totalMoves++;
                  V[start + stop] = V[start]; totalMoves++;
                  V[start] = temp; totalMoves++;
                  flag = 1;
              }
        }
    }
return;
}

//how i am calling
         shellSort(V, 0, size);

Here is some of my output for the shell sort
Elements	Compares	Moves	        Time
128	            281517372	398001528	10084
256	           264693303	395451665	 9882
512	          251344329	390291230	9578
1024	          227264865	379950123	9227
2048	         187358061	359247672	8283
4096	        132653775	317822533	6947
8192	         78654387	234952018	4871
16384	          48631917	209608355	4081
Somethins is flakey here...

**dwks** · 11-18-2005

You don't need a return at the end of a void function.

Code:

for (start = 0; start < (V.size() - stop); start++){

Is that what you want?

**TheSpoiledMilk** · 11-22-2005

will having a return at the end of this void function really make the performance go as high as O(n^2)? I need to know what is causing the shell sort to take so long.

**Daved** · 11-22-2005

No, the return statement won't affect performance, it just isn't necessary.

**Darryl** · 11-22-2005

Ok let's take a look:

Code:

void shellSort(vector<Wrd>& V, int start, int stop)
{
	bool flag = true;
	Wrd temp;

	while( flag || (stop > 1))
	{
		flag = false;
		stop = (stop + 1) / 2;
		int loopend = V.size()-stop;
		int startstop = start+stop;
		for (start = 0; start < loopend; start++)
		{
			if (compare(V[startstop], V[start]))
			{
				temp = V[startstop]; 
				V[startstop] = V[start]; 
				V[start] = temp; 
				totalMoves+=3;
				flag = true;
			}
		}
	}
	return;
}

a few optimizations

Thread: Shell Sort with Vectors Problem

Thread Tools

Search Thread

Display

Shell Sort with Vectors Problem

Similar Threads

Bubble Sort Code Problem...

Simulating a shell problem

Using Vectors (cont) - Sort Problem

Insertion Sort Problem

programming unix shell piping problem