Shell Sort with Vectors Problem

This is a discussion on Shell Sort with Vectors Problem within the C++ Programming forums, part of the General Programming Boards category; I have a program that compares the # of moves # of compares and the total time it take to ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    6

    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. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    6
    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. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    No, the return statement won't affect performance, it just isn't necessary.

  5. #5
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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
    Last edited by Darryl; 11-22-2005 at 02:07 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubble Sort Code Problem...
    By h4rrison.james in forum C Programming
    Replies: 7
    Last Post: 01-22-2009, 06:43 AM
  2. Simulating a shell problem
    By Galileo in forum Linux Programming
    Replies: 1
    Last Post: 06-06-2008, 04:41 AM
  3. Using Vectors (cont) - Sort Problem
    By clegs in forum C++ Programming
    Replies: 2
    Last Post: 09-17-2007, 06:31 AM
  4. Insertion Sort Problem
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-08-2005, 12:30 PM
  5. programming unix shell piping problem
    By Kyro in forum Linux Programming
    Replies: 2
    Last Post: 08-28-2003, 07:52 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21