C++

Forum

 
Sorting vector via recursive function

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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 

1
2
3
4
 
void numbers::sort_down()
{
     numbers = sort_down(numbers);
}
function in order to call this function

1
2
 
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!!!
satchmo05 (118)
OK, so I have a better way of posing my question:

Like I said before, I am new to recursive functions and I'm probably not really thinking in the correct way, but I would like to turn this for loop of a sorting function from max. to min. into a recursive function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
void numbers::sort_down()
{
    numbers = sort_down(numbers);
}

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] << " ";
}


Thanks for all of the help!! Let me know if you need more code. Thanks!
helios (17511)
You mean like quick sort?
satchmo05 (118)
I don't know what you mean by that. can you give me an example in context please?! Thanks for the help
helios (17511)
satchmo05 (118)
i think that just made it a whole lot more confusing
kempofighter (1183)
Well it's a confusing subject. Unless you are a mathematician writing a paper on the various kinds of sorting algorithms it'd probably be best to just use the std::stable_sort or std::sort. The wiki link provides an example implementation. There are others on the web that you can study and debug if you'd like. It's best not to reinvent the wheel unless you are actually planning on designing a sort that is better than any other. If you are truly a beginner programmer it's best to debug existing programs and study them. You'll waste a lot of time trying to second guess the mathematicians.
satchmo05 (118)
i understand, but now that I'm sort of close, I want to get this right, not to second guess you or anything. your points are valid. ;)

Below is my revised code, I have two problems I need answered:

1.) While running, the program says that it has to close down due to an unexpected warning. I don't know if this is a possibility or not, but am I accessing memory I shouldn't be?! What is the problem spot in my code that is doing this?

2.) When I uncomment the last line (line 55) in the
vector <int> numbers::sort_up
function, I get an infinite recursion problem, yet I do not know why either. I've tried mapping it out and being my own debugger, but I don't see it. An extra set of eyes would be very helpful.

Thank you for all the help!!! I know most of you don't want to see all of my code, but it could help you to find where the problem is. Thanks again! Much appreciated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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);
};

void numbers::add(int n)
{
    if (n > 0)
       numbers.push_back(n);
    else 
    {
       cout << "Invalid value, must be greater than zero";
       exit(1);
    }
}

int numbers::remove(int index)
{
    if ((index >= 0) && ((index + 1) <= numbers.size()))
       numbers.erase(numbers.begin() + index);
    else
    {
        cout << "Invalid index";
        //exit(1);
    }
}

void numbers::sort_up()
{
	numbers = sort_up(numbers);
}

void numbers::sort_down()
{
    numbers = sort_down(numbers);
}

vector <int> numbers::sort_up(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;
                  }
              }
              //cout << unsorted_list[i] << " ";
          }
          numbers::remove(unsorted_list[unsorted_list.size() - 1]);
          //numbers::sort_up(unsorted_list);
      }
}


vector <int> numbers::sort_down(vector <int> unsorted_list)
{
      if(unsorted_list.size() == 1)
          cout << unsorted_list.at(0);
      else 
      {
      
      
      }
}

void numbers::get()
{
    int next;
    ifstream in_file;
	in_file.open("numbers.dat");
	
    if (in_file.fail())
	{
       cout << "Failed to open file." << endl;
       exit(1);
    }
    
    while (in_file >> next)
    {
       numbers.push_back(next);
       next++;
    }
    in_file.close();
}
void numbers::display()
{
    for (int j = 0; j < numbers.size(); j++)
        cout << numbers[j] << " ";
    cout << endl;
}

int main()
{
	int number, input, next;
	char answer;
    numbers our_numbers;
    our_numbers.get();
    
    do {
    cout << endl << "1. Add a number to the end of the vector" << endl << "2. Remove a value at a specified index in the vector" << endl << "3. Sort the vector from lowest to highest" << endl << "4. Sort the vector from highest to lowest" << endl << "Please select the option that you would like to complete: ";
    cin >> number;
    if (number == 1)
    {
       cout << endl << "Please enter a number to add to the end of the vector: ";
       cin >> input;
       our_numbers.add(input);
       cout << "Unsorted vector: ";
       our_numbers.display();
    }
    else 
         if (number == 2)
         {
            cout << endl << "Please enter an index of the vector to remove: ";
            cin >> input;
            our_numbers.remove(input); 
            cout << endl << "Unsorted vector: ";
            our_numbers.display();
         }
         else 
              if (number == 3)
              {
                 cout << endl << "Unsorted vector: ";
                 our_numbers.display();
                 cout << "Sorted vector: ";
                 our_numbers.sort_up();
              }
              else 
                   if (number == 4)
                   {
                      cout << endl << "Unsorted vector: ";
                      our_numbers.display();
                      cout << "Sorted vector: ";
                      our_numbers.sort_down();
                   }
                   else
                   {
                       cout << endl << "Invalid value. Program exiting...";
                       exit(1);
                   }
                   
    cout << endl << "Would you like to test another operation? <y/n> : ";
    cin >> answer;
    } while (answer == 'Y' || answer == 'y');
   return 0;
}
Hammurabi (399)
You do realize that you can (and should) split long lines over multiple lines, right? And you don't have to use endl for newlines. Look how much nicer this is:

1
2
3
4
5
 
cout << "\n1. Add a number to the end of the vector"
     << "\n2. Remove a value at a specified index in the vector"
     << "\n3. Sort the vector from lowest to highest"
     << "\n4. Sort the vector from highest to lowest"
     << "\nPlease select an option: ";

satchmo05 (118)
yes, i do know that. are you able to help me by chance?
kempofighter (1183)
The structure of the if..elseif is totally wrong. I don't like the fact that a lot of your else statements don't have brackets even though there is another block of if..else statements within each else. 

1
2
3
4
5
6
7
8
9
10
11
12
 
if(1== number)
{
}
elseif(2 == number)
{
}
elseif(3 == number)
{
}
else
{
}


Shouldn't this return if size is 1? Exit will end the program completely.
1
2
3
4
5
 
 if(unsorted_list.size() == 1)
      {
         cout << unsorted_list.at(0);
         exit(1);
      }


Your exit problem is probably associated with the fact that you are using exit. You aren't printing a lot of useful debug info in those cases.

The sort function doesn't make any sense to me. It looks like you took your original sort and kept the for loops and then just called the function recursively over and over. What do you think will cause the function to stop calling itself? At some point, the function has to realize that it is finished so that it can simply return and not keep calling itself infinitely. You're also calling remove within the sort function which makes no sense. Why are you removing data from the array? This is supposed to sort and shouldn't be removing anything. You need to go look at the quick sort examples on the internet and study them so that you can understand the concept of recursion.

satchmo05 (118)
Ok, I have myself a new and improved (kinda) program that is working much better, but still has some problems that I would like to ask for help. I have two questions:

1.) When I choose option 3 (sort up) or option 4 (sort down), It displays the tree of numbers but then after it outputs the last integer, I get a new window that pops up on a Windows computer that says
A problem caused the program to stop working correctly
and the program closes. On a Unix-based computer, I had received an error that says:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
92Aborted
Can someone enlighten me to the solution to this problem please?

2.) As you can tell by my code that my running program outputs an integer tree whose size decreases by one after it removes the max/min value in each modified vector. I would like for the sorted vector just to output the max and min value without the remaining values. Can someone please modify my code to achieve this?

Thank you very much for all help!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
#include <iostream>
#include <vector>
#include <fstream>
#include <stdlib.h>

using namespace std;

class numbers
{
   public:
        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 function 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_down(vector <int> unsorted_list);
        vector <int> sort_up(vector <int> unsorted_list);
};

void numbers::add(int n)
{
    if (n > 0)
    {
        numbers.push_back(n);
        for (int i = 0; i < numbers.size(); i++)
           cout << numbers[i] << " ";
    }
    else
    {
       cout << "Invalid value, must be greater than zero";
       exit(1);
    }
}

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] << " ";
        cout << endl;
    }
    else
    {
        cout << "Invalid index, element either below zero or has exceeded the size of the array";
        cin.get();
    }
}

void numbers::sort_down()
{
    numbers = sort_down(numbers);
}

void numbers::sort_up()
{
        numbers = sort_up(numbers);
}

vector <int> numbers::sort_down(vector <int> unsorted_list)
{
      int count = 0;
      if (unsorted_list.size() == 1)
         cout << unsorted_list[0];
      else
      {
          int max = unsorted_list[0];
          for (int i = 0; i < unsorted_list.size(); i++)
          {
              if (max < unsorted_list[i])
              {
                 max = unsorted_list[i];
                 count = i;
              }
          }
          cout << max << " -- ";
          numbers::remove(count);
          numbers::sort_down();
      }
}

vector <int> numbers::sort_up(vector <int> unsorted_list)
{
      int count = 0;
      if (unsorted_list.size() == 1)
         cout << unsorted_list[0];
      else
      {
          int min = unsorted_list[0];
          for (int i = 0; i < unsorted_list.size(); i++)
          {
              if (min > unsorted_list[i])
              {
                 min = unsorted_list[i];
                 count = i;
              }
          }
          cout << min << " -- ";
          numbers::remove(count);
          numbers::sort_up();
      }
}

void numbers::display()
{
    int next;
    ifstream in_file;
        in_file.open("numbers.dat");
       
    if (in_file.fail())
        {
       cout << "Failed to open file." << endl;
       exit(1);
    }
   
    while (in_file >> next)
    { 
       numbers.push_back(next);
       next++;
    }
    in_file.close();
    
    for (int j = 0; j < numbers.size(); j++)
        cout << numbers[j] << " ";
    cout << endl;
}

int main()
{
    int number, input;
    char answer;
    numbers our_numbers;
    
    cout << "Unsorted vector: " << endl;
    our_numbers.display();
   
    do {
    cout << "1. Add a number to the end of the vector" << endl
         << "2. Remove a value at a specified index in the vector" << endl
         << "3. Sort the vector from lowest to highest" << endl
         << "4. Sort the vector from highest to lowest" << endl
         << "Please select the option that you would like to complete: ";
    cin >> number;
   
    if (number == 1)
    {
       cout << "Please enter a number to add to the end of the vector: ";
       cin >> input;
       cout << "New vector: " << endl;
       our_numbers.add(input);
    }
      
    else if (number == 2)
    {
       cout << "Please enter an index of the vector to remove: ";
       cin >> input;
       cout << "New vector: " << endl;
       our_numbers.remove(input);
    }
    else if (number == 3)
    {
       cout << "Sorted vector: " << endl;
       our_numbers.sort_up();
    }
    else if (number == 4)
    {
       cout << "Sorted vector: " << endl;
       our_numbers.sort_down();
    }
    else
    {
       cout << endl << "Invalid value. Program exiting...";
       exit(1);
    }
                  
    cout << "Would you like to test another operation? <y/n> : ";
    cin >> answer;
    } while (answer == 'Y' || answer == 'y');
   
    cin.get();
    return 0;
}
Topic archived. No new replies allowed.