Thread: Sort Function

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    127

    Sort Function

    Hey,

    Can anyone help me with the development of the below sortPercentage function?

    Code:
    #include <stdlib.h>
    
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <stdlib.h>
    
    #include "dataobject.h"
    
    using namespace std;
    
    int randNum();
    
    template <class iterator> 
       void sortPercentage(iterator start, iterator finish, int percentage);
    
    template <class iterator> 
       void sortContainer(iterator start, iterator finish, int gap);
       
    
    int randNum()
    {
       // rand() produces pseudo-random number in range 0 to RAND_MAX
       // for most compilers RAND_MAX is 2^15-1
       // randNum() produces pseudo-random number in range 0 to 2^31-1
      
       return ((rand() << 16) + rand());
    } 
    
    template <class iterator> 
       void sortPercentage(iterator start, iterator finish, int percent);
    {
       /**************************************************  ***********************\
          sortPercentage
          Checks every consecutive pair of items in the container, 
          eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
          and finds the percentage that are in order vs the total number of pairs.
          This percentage value is returned.
       \*************************************************  ************************/
     
    
    }
    
    
    
    
     
    template <class iterator> 
       void sortContainer(iterator start, iterator finish, int gap)
    {
       /**************************************************  **************\
           Sort the container using shell sort
           gap will be called with the original size of the container
           The underlying sort for the container is bubble sort which
           will be run twice for each gap decrement
       \*************************************************  ***************/
    
       if (gap == 1) return;
       
       iterator left, right;
       int i, numswap, totswap=0, numpass, sortPercent;
       
       gap = gap * 3 / 4;
       do {
          numswap = 0;
          
          // Reduce gap. Gap will start out at half the size of the container
          // Eventually will stabilize at 1 in size
          gap = (gap * 2 + 1) / 3; 
          
          // make two passes through container with bubble sort
          for (numpass=0; numpass<2; numpass++) {
             right = left = start;
             // Make the distance between left and right gap in size
             for (i=0; i<gap; i++) right++;
             
             // Make a pass through container using Bubble sort
             while (right != finish) {
                if (*left < *right) {
                   swap(left, right);
                   numswap++;
                }
                left++;
                right++;
             }
          
             // update some statistics and print them
             totswap += numswap;
             cout << "gap = " << gap << " num swaps = " << numswap;
             cout << " sort percentage = " << sortPercent(start, finish) << "\n";
             
             if (numswap == 0) break;
          }
       } while (numswap > 0 || gap > 1);
       
       cout << "Total swaps = " << totswap << "\n";
    }
    
    int main(int argc, char *argv[])
    {
       const int MAXDATA = 10000;
       vector<dataObject> array;
       dataObject *doPtr;
       int i, rand;
       
       try {
          /**************************************************  ************\
             Initialise things to demonstrate the sort
          \*************************************************  *************/
          
          // fill vector with unique values
          for (i=0; i<MAXDATA; i++) {
             doPtr = new dataObject(i);
             array.push_back(*doPtr);
             delete doPtr;
          }
          
          // set up random number generator
          if (argc != 2) {
             cout << "Syntax : program seed\n";
             cout << "seed is any integer value\n";
             return 0;
          }
          int seed = atoi(argv[1]);
          srand(seed);
          
          // scramble vector
          for (i=0; i<MAXDATA; i++) {
             rand = randNum() % MAXDATA;
             swap(array[i], array[rand]);
          }
          cout << MAXDATA << " Items in vector\n";
          
          /**************************************************  ***********\
             sort the vector using iterators 
          \*************************************************  ************/
          
          cout << "Sorting vector using shell sort\n";
          sortContainer(array.begin(), array.end(), array.size());
          
       } catch(...) {
          cout << "\nERROR - undefined Exception thrown\n";
          exit(1);
       }
       
       return 0;
    }
    Code:
    #ifndef DATAOBJECT_H_
    #define DATAOBJECT_H_
    
    #include <algorithm>
    
    /**************************************************  *********\
       class for holding data to be stored in container objects
    \*************************************************  **********/
    
    struct dataObject
    {
       int keyval;
       
       /**************************************************  ******\
          place any other data declartions the data object 
          may need here
       \*************************************************  *******/
       
       /**************************************************  ******\
          constructors
       \*************************************************  *******/
       
       // constructor
       dataObject() : keyval(-1) {}
       dataObject(int val) : keyval(val) {}
       
       // copy constructor
       dataObject(const dataObject &other) : keyval(other.keyval) {
          // copy any data in other to this
       }
       
       /**************************************************  ******\
          misc functions
       \*************************************************  *******/
       
       void swapObjects(dataObject &other) {
          std::swap(keyval, other.keyval);
          // swap any other data in dataObject
       }
       
       bool isKeyval(int val) const {
          return (val == keyval);
       }
       
       int getKeyval() const {
          return keyval;
       }
       
       int getHashval(int range) const {
          return (keyval % range);
       }
    
       bool empty() const {
          return (keyval == -1);
       }
       
       /**************************************************  ******\
          overloaded operators
       \*************************************************  *******/
       
       // overloaded assignment operator
       dataObject& operator = (const dataObject &other) {
          dataObject temp(other);
          swapObjects(temp);
          return *this;
       }
       
       // overloaded relational operators
       bool operator == (const dataObject &other) const {
          return (keyval == other.keyval);
       }
       
       bool operator != (const dataObject &other) const {
          return (keyval != other.keyval);
       }
       
       bool operator > (const dataObject &other) const {
          return (keyval > other.keyval);
       }
       
       bool operator < (const dataObject &other) const {
          return (keyval < other.keyval);
       }
       
       bool operator >= (const dataObject &other) const {
          return (keyval >= other.keyval);
       }
       
       bool operator <= (const dataObject &other) const {
          return (keyval <= other.keyval);
       }
    };
    
    #endif

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    template <class iterator> 
       void sortPercentage(iterator start, iterator finish, int percent /*???*/);
    {
       /**************************************************  ***********************\
          sortPercentage
          Checks every consecutive pair of items in the container, 
          eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
          and finds the percentage that are in order vs the total number of pairs.
          This percentage value is returned.
       \*************************************************  ************************/
     
    
    }
    There are problems with the prototype but the implementation should be quite trivial.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    Code:
    template <class iterator> 
       int sortPercentage(iterator start, iterator finish);
    Would the above be better?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Yes that looks better. You nees to make a start on the contents of the function now before we can give you much more help on it. As for the rest of it though - some other tips:

    You're missing an opportunity to take advantage of random-access iterators, by using a loop to increment 'right' by 'inc' where you could be using std::advance.
    Should 'swap' not swap *left and *right? Or does swapping iterators themselves actually do what you want? I must admit I've never tried that.

    Comb Sort usually decreases the gap to 10/13ths of what it was each time rather than 2/3rds. You may find that often a lot of passes with a gap of 1 end up being required.
    It's also highly unorthodox to make two passes through the data for each gap width, but I guess that could be how you're lessening the problem I just mentioned. I'm sure the normal way of implementing it works much better overall.

    Don't new up and then delete something just to insert it into a vector:
    Code:
          for (i=0; i<MAXDATA; i++) {
             doPtr = new dataObject(i);
             array.push_back(*doPtr);
             delete doPtr;
          }
    You should just be using the stack like this:
    Code:
          for (i=0; i<MAXDATA; i++) {
             array.push_back(dataObject(i));
          }
    And finally, don't implement the assignment operator or copy-constructor (or destructor for that matter), for any class that will already do the right thing when these are left unimplemented. More code equals more room for bugs. If you add an other members to the class and forget to update both of these you'll get a bug that could take quite a while to track down. If you leave them unimplemented instead then they'll just continue to work. If at some point you later introduce a member that requires different copying behaviour (such as a raw pointer to an owned array), then that's the point at which you should perhaps implement these.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    Would something like the below do the job properlly?

    Its just the raw so I'd have to edit to fit it to the spec but I'm just trying to work out the logic first.

    Code:
    bool Changed = true;
    int Passes = 0;
    while(Changed)
    {    
        if Changed = false;
           passes++;
    
        for(int j = 0; j < arraySize -1; j++)
        {
            if(a[j] > a[j+1])
            {
                Changed = true;
                int hold = a[j];
                a[j] = a[j+1];
                a[j+1] = hold;
            }
        }
    }

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I think the idea is to not make any change to the array contents. As far as I can see it's supposed to return some measure of presortedness.

    I think they just want you to count up the number of adjacent items that are out of order versus how many adjacent pairs there are.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    Ok yeah I think you're right. So in that case I would just remove the swap function from the check right?

    Code:
    bool Changed = true;
    int Passes = 0;
    while(Changed)
    {    
        if Changed = false;
           passes++;
    
        for(int j = 0; j < arraySize -1; j++)
        {
            if(a[j] > a[j+1])
            {
                Changed = true;
            }
        }
    }

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Closer. You want to actually count how many times, i.e. increment a count rather than simply setting something to true.
    Then to get a percentage, you need to work out how many pairs of items there are.
    Then you need a formula for percentage. Something like: 100 * count / total

  9. #9
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    Isn't the passes my count though?

    Code:
    bool Changed = true;
    int Passes = 0;
    while(Changed)
    {    
        if Changed = false;
           passes++;
    
        for(int j = 0; j < arraySize -1; j++)
        {
            if(a[j] > a[j+1])
            {
                Changed = true;
            }
        }
    }
    
    percentage = passes / (arraysize -1) * 100

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Why don't you compile and run your code?

    The general logic might work, but why make it so complicated? Why manipulate a boolean in complicated way, when you can just increment a counter at the same place where you determine that it needs to be incremented.

    Code:
    percentage = passes / (arraysize -1) * 100
    With integer math this might be always 0.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Code:
        if Changed = false;
           passes++;
    Did you want this to be an if statement or what?

    I also don't see why passes is a measure of presortedness. In that regard, sorting algorithms can take many "passes" more than what is optimal to sort something.

    I guess I would implement insertion sort and then calculate using the lengths of the unsorted and sorted ends.

  12. #12
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    How else would I do it? I thought the boolean would be a good way.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You don't need that while loop, just the for loop - sorry I was ignoring that it was even there before. You only need to go through the array once from start to finish and count how many pairs were out of order.

    anon is correct that you need to multiply by 100 before the division or else the last part evaulated will be either 0 * 100 or 1 * 100.

    Another hint: You don't need to count the number of pairs there are, it's just one subtraction to get that answer.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Aug 2006
    Posts
    127
    So I've edited the code and it compiles but when I run it I get the below error:

    ./a.out 32
    10000 Items in vector
    Sorting vector using shell sort
    Segmentation Fault (core dumped)

    Any ideas on what I need to change so that I can get it to run?

    Code:
    /********************************************************\
       Test program for demonstrating sorting algorithms
    \********************************************************/
    #include <stdlib.h>
    
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <stdlib.h>
    
    #include "dataobject.h"
    
    using namespace std;
    
    int randNum();
    
    template <class iterator> 
       void sortContainer(iterator start, iterator finish, int gap);
       
    
    int randNum()
    {
       // rand() produces pseudo-random number in range 0 to RAND_MAX
       // for most compilers RAND_MAX is 2^15-1
       // randNum() produces pseudo-random number in range 0 to 2^31-1
      
       return ((rand() << 16) + rand());
    } 
    
    template <class iterator>
       int sortPercentage(iterator start, iterator finish)
    {
       /*************************************************************************\
          sortPercentage
          Checks every consecutive pair of items in the container, 
          eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
          and finds the percentage that are in order vs the total number of pairs.
          This percentage value is returned.
       \*************************************************************************/
     
       iterator left, right;
       int InnerCount;
       int comparisons;
       int swaps = 0;
    
       for (comparisons = 0; comparisons < finish; comparisons++)
       {
          for (InnerCount = 0; InnerCount < finish; InnerCount++)
          {
             right = left = start;
    
             while (right != finish)
             {
                if (*left < *right)
                {
                   swaps+=1;
                }
             }
          }
          comparisons+=1;
       }
    }
    
    template <class iterator> 
       void sortContainer(iterator start, iterator finish, int gap)
    {
       /****************************************************************\
           Sort the container using shell sort
           gap will be called with the original size of the container
           The underlying sort for the container is bubble sort which
           will be run twice for each gap decrement
       \****************************************************************/
    
       if (gap == 1) return;
       
       iterator left, right;
       int i, numswap, totswap=0, numpass, sortPercent;
       
       gap = gap * 3 / 4;
       do {
          numswap = 0;
          
          // Reduce gap. Gap will start out at half the size of the container
          // Eventually will stabilize at 1 in size
          gap = (gap * 2 + 1) / 3; 
          
          // make two passes through container with bubble sort
          for (numpass=0; numpass<2; numpass++) {
             right = left = start;
             // Make the distance between left and right gap in size
             for (i=0; i<gap; i++) right++;
             
             // Make a pass through container using Bubble sort
             while (right != finish) {
                if (*left < *right) {
                   swap(left, right);
                   numswap++;
                }
                left++;
                right++;
             }
          
             // update some statistics and print them
             totswap += numswap;
             cout << "gap = " << gap << " num swaps = " << numswap;
    //         cout << " sort percentage = " << sortPercent(start, finish) << 
    "\n";
             
             if (numswap == 0) break;
          }
       } while (numswap > 0 || gap > 1);
       
       cout << "Total swaps = " << totswap << "\n";
    }
    
    int main(int argc, char *argv[])
    {
       const int MAXDATA = 10000;
       vector<dataObject> array;
       dataObject *doPtr;
       int i, rand;
       
       try {
          /**************************************************************\
             Initialise things to demonstrate the sort
          \**************************************************************/
          
          // fill vector with unique values
          for (i=0; i<MAXDATA; i++) {
             doPtr = new dataObject(i);
             array.push_back(*doPtr);
             delete doPtr;
          }
          
          // set up random number generator
          if (argc != 2) {
             cout << "Syntax : program seed\n";
             cout << "seed is any integer value\n";
             return 0;
          }
          int seed = atoi(argv[1]);
          srand(seed);
          
          // scramble vector
          for (i=0; i<MAXDATA; i++) {
             rand = randNum() % MAXDATA;
             swap(array[i], array[rand]);
          }
          cout << MAXDATA << " Items in vector\n";
          
          /*************************************************************\
             sort the vector using iterators 
          \*************************************************************/
          
          cout << "Sorting vector using shell sort\n";
          sortContainer(array.begin(), array.end(), array.size());
          
       } catch(...) {
          cout << "\nERROR - undefined Exception thrown\n";
          exit(1);
       }
       
       return 0;
    }
    Last edited by Taka; 05-22-2009 at 08:28 PM. Reason: Code addition

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Okay I had just told you how "You don't need that while loop, just the for loop" but you've done the opposite of removing that loop - you've added yet another nested loop to the function.

    I can also see from your latest code that you've actually completely ignored everything I have said.

    So since when helped you if anything go backwards, I'm going to stop helping you now, in case by some miracle you then actually go forwards and get closer to the goal. Best of luck.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-13-2011, 08:28 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Compile problem: sort() cannot be used as a function!?
    By ac251404 in forum C++ Programming
    Replies: 2
    Last Post: 06-01-2006, 12:58 PM
  4. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  5. Replies: 10
    Last Post: 09-15-2004, 01:00 PM