Sorting vector via recursive functions

This is a discussion on Sorting vector via recursive functions within the C++ Programming forums, part of the General Programming Boards category; I agree that this is a bad way to learn recursion, but here's a few ideas : I think you'll ...

  1. #16
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    I agree that this is a bad way to learn recursion, but here's a few ideas :

    I think you'll have to pass a length into the sort function that's separate from the list length. That way you can turn the outer loop into a recursive call to your function, passing size - 1 each time.

    If your homework requires that you use the exact prototypes given, you'll have to play games with only passing the unsorted beginning elements of the vector into each subsequent recursive call and then pushing back the sorted elements as you return from each recursive call.

    As others have said, this isn't the most straightforward way of learning about recursion.

  2. #17
    Registered User
    Join Date
    Apr 2009
    Location
    ...creepy
    Posts
    75
    So, I've been tweaking some of my program, and I am getting stuck in an infinite loop and this is because I'm not decrementing my recursive function by one, I know this. However, when I am calling my remove function inside my sort function, shouldn't the size of the vector be decrementing by one each time?! I don't understand why I'm getting caught up in an infinite loop....can someone try to fix my code for me please!!!

    Code:
    int numbers::remove(int index)
    {
        if ((index >= 0) && ((index + 1) <= numbers.size()))
        {
            numbers.erase(numbers.begin() + index);
            for (int i = 0; i < numbers.size(); i++)
                cout << numbers[i] << " ";
        }
        else
        {
            cout << "Invalid index, element either below zero or has exceeded the size of the array";
            exit(1);
        }
    }
    
    vector <int> numbers::sort(vector <int> unsorted_list)
    {
          int i = 1;
          if(unsorted_list.size() == 1)
          {
             cout << unsorted_list.at(0);
             exit(1);
          }
          else
          {
              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;
                      }
                  }
              }
              numbers::remove(unsorted_list.size() - 1);
              for (int k = unsorted_list.size() - 1; k >= 0; k--)
                  cout << unsorted_list[k] << " ";          
              numbers::sort(unsorted_list);
          }
    }
    Thanks for all of the help!!! If you need more code to look at, let me know. Thanks again!

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    1. Turn your compiler's warning level up to the max.
    2. Fix the fact that none of the control paths return a value, in either function!
    3. Why would a sort function EVER remove an item from the container!?!
    4. You're not even removing an item from the same container as the sort function, although surely that can't even compile because numbers is being used as both a variable AND a type!
    5. It's horridly ineficient to pass the vector by value (amoungst other things), and this function, if it worked, would be about O(n^4).

    The only bit right with that code is the bubble sort (though the comments for it are all wrong), and you can't usefuly make bubble sort recursive.
    Oh I guess the indentation is right too, I'll give you that.

    Go back an learn about classes and functions again. The best thing you can do with that code is select it all and press the delete key.
    Again, what algorithm do you plan on implementing recursively?
    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"

  4. #19
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Read and understand the previous post first, especially the part about returning values from methods.

    I still think it's a bad idea to code a bubble sort like this, but if you insist :

    To translate to a recursive function, remove a loop from the iterative function and turn it into a recursive call instead. You've left the loop in and then added a recursive call on top of that.

    To erase the last element, look at the pop_back() method. There's a corresponding push_back() to put something back on the end of the list.

    Here's a basic outline

    if list size is less than or equal to 1, return the list since a list that size is already sorted.

    Go through the list in order, doing the inner loop of a normal bubble sort. This will push the biggest element to the end of the list.

    Save the element at the end of the list (list.back()), then remove it from the list
    call sort with this new shorter list
    put the saved element back on the end of the list and return it.

Page 2 of 2 FirstFirst 12
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

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