# Shell Sort with Vectors Problem

• 11-17-2005
TheSpoiledMilk
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...```
• 11-18-2005
dwks
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?
• 11-22-2005
TheSpoiledMilk
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.
• 11-22-2005
Daved
No, the return statement won't affect performance, it just isn't necessary.
• 11-22-2005
Darryl
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