Thread: Sorting vector via recursive functions

  1. #1
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75

    Sorting vector via recursive functions

    OK, so here is a basic for loop sorting function that I have coded prior to my current program:

    Code:
    float max; 
          int temp; 
          for (int i = array_size - 1; i >= 0; i--) // Reading the dataset starts backwards. 
          {
              for (int j = 0; j < array_size - 1; j++) 
              {
                  if (array[j] > array[j+1]) //Switching values to maximize convenience. 
                  { 
                     temp = array[j]; 
                     array[j] = array[j+1]; 
                     array[j+1] = temp; 
                  } 
              } 
          }
    It works, so I like it. However, with my current program, I would like to test the waters using recursive functions. Unfortunately, I have hit a brick wall and that's where I come to you all for help. Here is my class that I am using for this program:

    Code:
    class numbers
    {
    public:
        void get();            // Stores input file values to vector <int> number
    	void add(int n);       // Adds a new number to the end of the vector
    	int remove(int i);     // Removes the element at the specified index of the vector
    	void sort_up();        // Calls the private recursive sort_up function
    	void sort_down();      // Calls the private recursive sort_down function
    	void display();        // Prints the vector to the screen
    	
    private:
    	vector <int> numbers;
    	vector <int> sort_up(vector <int> unsorted_list);
        vector <int> sort_down(vector <int> unsorted_list);
    };
    My problem is that I do not know the code I should be using in my
    Code:
    void numbers::sort_down()
    {
         numbers = sort_down(numbers);
    }
    function in order to call this function
    Code:
    vector <int> numbers::sort_down(vector <int> unsorted_list)
    { }
    in order to sort from max. to min. All help is appreciated!!! Thank you very much. If you would like to see my entire code in order to grasp, I will copy and paste it in as soon as I can. Thank you again!!!

  2. #2
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Not directly related to your question, but you can change:
    Code:
    if (array[j] > array[j+1]) //Switching values to maximize convenience. 
    {
        temp = array[j]; 
        array[j] = array[j+1]; 
        array[j+1] = temp; 
    }
    to:
    Code:
    if (array[j] > array[j+1]) //Switching values to maximize convenience. 
    {
        std::swap( array[j], array[j+1] );
    }
    Now, why not use one of the sort algorithms in the STL instead of rolling your own?
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  3. #3
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    better practice, understanding how everything "under the hood" works

  4. #4
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    but do you know how to help me out by chance?!

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Can you explain what it is you don't know how to do?

    You need to walk through the array and compare the elements. Whether you do this via recursion or loops doesn't really matter.

    The general case for recursion is that you have a problem that is, under some circumstances is easy to solve, e.g. sorting two numbers is fairly easy - it's a compare and a swap. So how can you make your sort function perform a sort of just two numbers from a large vector?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    well recursive functions are supposed to take a for loop and consolidate them down considerably to make it easier for the programmer and the program ultimately run a tad faster. so to optimize the speed of the program, I really want to know how to use recursive functions in order to sort through this vector. @ matsp, does this make sense? can you lay down a starting piece of code that would put me in the right direction please?! Thanks for the help!

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by porsche911nfs View Post
    well recursive functions are supposed to take a for loop and consolidate them down considerably to make it easier for the programmer and the program ultimately run a tad faster. so to optimize the speed of the program, I really want to know how to use recursive functions in order to sort through this vector. @ matsp, does this make sense? can you lay down a starting piece of code that would put me in the right direction please?! Thanks for the help!
    Using recursion is almost never faster.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    oh, well regardless of the optimization, i would like to know how to turn this private member function into a recursive function. I want to test the waters, so I know how to do it if need be in the future. Thanks for the help!!! Here is what I have so far that needs to be converted:

    Code:
    vector <int> numbers::sort_down(vector <int> unsorted_list)
    {
          int temp; 
          for (int i = unsorted_list.size() - 1; i >= 0; i--) // Reading the dataset starts backwards. 
          {
              for (int j = 0; j < unsorted_list.size() - 1; j++) 
              {
                  if (unsorted_list[j] > unsorted_list[j+1]) //Switching values to maximize convenience. 
                  { 
                     temp = unsorted_list[j]; 
                     unsorted_list[j] = unsorted_list[j+1]; 
                     unsorted_list[j+1] = temp; 
                  } 
              } 
          } 
          for (int i = unsorted_list.size() - 1; i >= 0; i--)
              cout << unsorted_list[i] << " ";
    }
    This code is the for loop for what you would expect from a sort from max. to min. loop, but I would like to convert this to a recursive. Thanks for everyone's help!

  9. #9
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    oh yeah, and then this if this is relevant:

    Code:
    void numbers::sort_down()
    {
        numbers = sort_down(numbers);
    }
    thanks again!

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You obviously will need to do SOMETHING to modify the numbers (at least sometimes) in your sort_down() function. How can you determine if the list is sorted? How can you determine if two elements need swapping.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    If you want to learn how to use recursion, this is a very bad example to use it on, since trying to turn this sort function into a recursive function would almost certainly be MUCH more complicated and a LOT slower.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  12. #12
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    its OK, i'm up for it. would you know a way to get me started cpjust?

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by porsche911nfs View Post
    its OK, i'm up for it. would you know a way to get me started cpjust?
    If you want a real example of a recursive algorithm, we can give you several, but I don't think anybody is going to spend any time on making a recursive bubble sort. Because of how bubble sort works, the recursion depth will be proportional to N and that makes it completely impractical for any real-world data set.

    A more naturally recursive sorting algorithm would be merge sort or quick sort.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    all i am asking for some one to give me a little push in the right direction with some code. Any little bit would help out a ton! I appreciate all of the help!

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by porsche911nfs View Post
    better practice, understanding how everything "under the hood" works
    Your endeavours will not tell you that at all.
    • std::sort can never be implemented as bubble sort.
    • There are not different algorithm functions to call to sort ascending or descending. The SC++L determines the sort direction using comparison functors passed as an argument to std::sort.
    • std::sort sorts in place rather than returning a sorted copy.

    Nope, I'm not buying that reason at all. If you want to know how it works, first learn how to use it and some of the theory behind it, then read the source code to it, and then try implementing it yourself.

    You clearly have some other agenda. I'm thinking something along the lines of an assignment that states you must sort a vector using recursion, considering you're so hell bent on using recursion. What algorithm do you plan on using, and when is your assignment due?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question regarding recursive functions
    By knj316 in forum C++ Programming
    Replies: 7
    Last Post: 10-01-2006, 11:41 PM
  2. Static member functions more efficient?
    By drrngrvy in forum C++ Programming
    Replies: 6
    Last Post: 06-16-2006, 07:07 AM
  3. Attaching functions to a class/struct
    By VirtualAce in forum Tech Board
    Replies: 2
    Last Post: 08-04-2003, 10:56 AM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. Recursive Functions
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 10-10-2001, 07:47 PM