# Thread: Sorting vector via recursive functions

1. ## 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. 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?

3. better practice, understanding how everything "under the hood" works

4. but do you know how to help me out by chance?!

5. 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

6. 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. Originally Posted by porsche911nfs
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.

8. 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. oh yeah, and then this if this is relevant:

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

10. 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

11. 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.

12. its OK, i'm up for it. would you know a way to get me started cpjust?

13. Originally Posted by porsche911nfs
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.

14. 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. Originally Posted by porsche911nfs
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?