C++

Forum

 
Sorting Code

angchan (6)
Hi all,
I'm having problem getting my code to work. I am trying to do a selection sort algorithm. I am required to sort a vector and give the maximum and minimum. If the vector contains only one value, it is both the minimum and maximum. If the vector contains two values, the values are compared. If the vector contains multiple values, the vector is split in two parts. The two parts will have a minimum and maximum and in the end they will be compared to generate one minimum and one maximum. I keep having a constant vector size errors and a number of other errors. I don't know what is causing this. Any suggestions would be helpful! Thank you

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
 
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int getMin(int a, int b);
int getMax(int a, int b);
void getVector(vector<int>&);
int compMin(vector<int>& userVect, int start, int end);
int compMax(vector<int>& userVect, int start, int end);
int main()
{
	
	
	vector<int> userVect;
	getVector(userVect);
	cout << "Maximum is: "<<compMin(userVect,userVect[0],userVect[userVect.size()-1]);
	cout << "Minimum is: "<<compMax(userVect,userVect[0],userVect[userVect.size()-1]);
	cin.ignore(2);
	return 0;
}

void getVector(vector<int>& newVect)
{
	int userInput;
	cout << "Please enter a list of numbers for divide and conquer with -1 to end:" << endl;
	cin >> userInput;

	while (userInput != -1)//a way to signal the end.
	{
		newVect.push_back(userInput);
		cin >> userInput;
	}
	cout << endl;
}

int getMin(int a, int b)
{
	if (a < b)
		return a;
	else 
		return b;
}
int getMax(int a, int b)
{
	if (a > b)
		return a;
	else
		return b;
}

//divide and conquer
//minimum divide conquer
int compMin(vector<int>& userVect, int start, int end)
{
	int min1=0;
	int min2=0;
	int mid;
	mid = (userVect.size()) / 2;
	//compare with 1 item
	if(userVect.size()==1)
	{
		min1=userVect[0];
	}
	//compare with 2 items
	else if (userVect.size() == 2)
	{
		getMin(userVect[0],userVect[1]);
	}
	else
	{
		//low range
		//intialize temp to store previous value
		for (int i = 0; i > mid - 1; i++)
		{
			min1 = compMin(userVect,userVect[i], userVect[i + 1]);
		}

		//high range 
		//warning for unsignedmismatch
		for (int j = mid + 1; j < userVect.size(); j++)
		{
			min2 = compMin(userVect,userVect[j], userVect[j + 1]);
		}
	}
	return getMin(min1, min2);
}
//max conquer 
int compMax(vector<int>& userVect, int start, int end)
{
	int max=0;
	int max2=0;
	int mid;
	mid = (userVect.size()) / 2;
	//compare with 1 item
	if (userVect.size() == 1)
	{
		max = userVect[0];
	}
	//compare with 2 items
	else if (userVect.size() == 2)
	{
		getMax(userVect[0], userVect[1]);
	}
	else
	{
		//low range
		for (int i = 0; i > mid - 1; i++)
		{
			max= compMax(userVect, userVect[i], userVect[i + 1]);
		}

		//high range 
		//warning for unsignedmismatch
		for (int j = mid + 1; j < userVect.size(); j++)
		{
			max2 = compMax(userVect, userVect[j], userVect[j + 1]);
		}
	}
	return getMax(max, max2);
}
Handy Andy (5051)
Hello angchan,

Welcome to the forum.

Some things I see right off.

Lines 9 and 10 Either change the comma to a semi-colon or remove "int" from in front of "start" and "end". When defining a list of variables you only need one type at the beginning of the line.

Line 19 Not sure why it is there? If it is to pause the program I would have to see it in action. Most times this is used: std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // <--- Requires header file <limits>.

A few well placed blank lines would help.

Not a big problem, but some people complain about #include "stdafx.h" . You and I both know that it is needed with VS, but it is best to leave it out when you post your code.

Beyond that I will have to load up the program and test it.

In the future if you have errors that you do not understand and can not figure out post the complete error message.

Hope that helps,

Andy
Handy Andy (5051)
Hello angchan,

Disregard what I said about lines 9 and 10. I now see that they are prototypes.

Andy
icy1 (596)
angchan, your recursive functions need more returns. Likely don't want that for loop in there, in addition to your recursion anyway.
Handy Andy (5051)
Hello angchan,

As icy1 pointed out the "compMin" and "compMax" functions ate recursive and thy do not need to be.

I changed to for loop around along with a couple of other things, see comments in code, and it works more like it should. Still have some refining to do because out of a vector of nine numbers the middle number is being skipped or missed.

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
 
int compMin(vector<int>& userVect, int start, int end)
{
	int min1 = userVect[0];  // Set to first element of vector.
	int min2 = 0;  // Initialized, but not set yet.
	int mid{};  //<--- Needed to be initialized.

	mid = (userVect.size()) / 2;

	min2 = userVect[mid + 1];  // <--- Set, but may not be the right subscript.

	//compare with 1 item
	if (userVect.size() == 1)
	{
		min1 = userVect[0];
	}
	//compare with 2 items
	else if (userVect.size() == 2)
	{
		getMin(userVect[0], userVect[1]);
	}
	else
	{
		//low range
		//intialize temp to store previous value
		for (int i = 0; i < mid - 1; i++)  // <--- Was > changed to <.
		{
			if (userVect[i] < min1)  // <--- Added.
				min1 = userVect[i];
			//min1 = compMin(userVect, userVect[i], userVect[i + 1]);
		}

		//high range 
		//warning for unsignedmismatch
		for (int j = mid + 1; j < userVect.size(); j++)
		{
			if (userVect[j] < min2)  // <--- Added.
				min2 = userVect[j];
			//min2 = compMin(userVect, userVect[j], userVect[j + 1]);
		}
	}
	return getMin(min1, min2);
}

The code for "compMax" needs to be changed.

The Warning that yo are getting is because your for loop counter "i" and "j" are defined as an "int", but "userVec.size()" returns a "size_t" which is an "unsigned int".

I changed my setup when typing for and then tab so that the code that comes out says:
for (std::size_t i = 0; i < length; i++). It is also set up so that "size_t", "i", "0" and length are all changeable and you can use the tab key to navigate through them. The other thing I do different is that I use "lc" in place of "i". If you are interested I will give you my changes and help you get it set up.

I have only worked on the min part, but the max part can use the same concept.

Having an odd number for the vector size means the one side would be larger than the other or in the case of this code the middle number is skipped so that each side has the same amount.

It appeared to me that as a recursive function with no way out it would be an endless loop always working with the same starting numbers because the for loops would never go past zero.

Hope that helps,

Andy
angchan (6)
HandyAndy- yeah I included the cin.ignore so it wouldn't close the program. I did this in the beginning and continued with it. I can take it out
Icy- I'm trying to compare by separating it into two parts, Should i do a separate recursion for the two different vecotrs? Is the for loop messing up the recursion?
icy1 (596)
angchan, upon further inspection, it seems you've misunderstood how the algorithm works, and so have run into a bunch of issues. Biggest mistakes were that you:
1. thought the array was getting smaller over time, which isn't true. The input array never changes; only the indices do.
2. were sending elements of the vector to the recursive function calls instead of sending indices.
3. had loops in the function. The function is supposed to call itself -- this is how it progresses and how it ends (with base cases). Doesn't need loops inside.

I'll explain it to you with i being the left index, and j the right index. These are the variables often used for indices in array algorithms like this. Suppose array is

vector<int> v = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};


We start by setting i to the starting index, and j to last index. This is a 10-element array, so i=0, j=9. Middle is (i+j)/2, or 4 with integer division.

1. We always choose (i, middle) for lower range.
2. We always choose (middle+1, j) for upper range.
3. Return max(lower range, upper range). Hint: use std::max !

Base cases:
1. When i==j we have a single element, so just return v[i]
2. When j-i==1 we have a difference of one, aka two elements; return max(v[i], v[j])


                        10, 9, 8, 7, 6, 5, 4, 3, 2, 1
                        i=0                         j=9

                                    mid=4
            10, 9, 8, 7, 6                         5, 4, 3, 2, 1
            i=0          j=4                       i=5         j=9

                 mid=2                                   mid=7

    10, 9, 8           7, 6                     5, 4, 3         2, 1
    i=0    j=2        i=3 j=4                  i=5   j=7       i=8,j=9
                    return max(7,6)                          return max(2,1)
       mid=1                                      mid=6

10,  9         8                               5, 4       3
i=0 j=1      i=2 j=2                         i=5 j=6    i=7 j=7 
max(10,9)    return 8                         max(5,4)   return 3
return 10                                     return 5



So code should look like this:
1
2
3
4
5
6
7
8
9
10
11
12
 
// Finds max using recursion and divide+conquer on a vector range
//   i - index from the left
//   j - index from the right
int MaxConquer(const vector<int>& v, int i, int j)
{
	if (i == j) { return v[i]; }
	if (j-i == 1) { return max(v[i], v[j]); }

	int mid = (i+j)/2;
	return max( MaxConquer( v, i, mid ),
	            MaxConquer( v, mid+1, j ) );
}


1
2
3
4
5
6
 
int main()
{
    vector<int> v = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    cout << "Maximum is: "<< MaxConquer(v, 0, v.size()-1) << endl;
    return 0;
}
Last edited on
angchan (6)
Icy- Ah I see now. The chart really helped. I didn't divide up the size of the vector to compare and I used the element instead of the indices for the functions(silly mistake). Thank you for your help ! Much appreciated :)
Topic archived. No new replies allowed.