# Thread: Shell Sort with Vectors Problem

1. ## Shell Sort with Vectors Problem

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...```

2. 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?

3. 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.

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

5. 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