I am trying to find the minimum value of an array using the "divide and conquer" methodology.
For this I have thought of ordering a matrix row by row, to later find its minimum values, but I have a problem:
My matrix is defined as map<int, map<int, int> >
and, when trying to apply the sort() function of the STL, it gives me an error.
My code is this:
for(int i = start; i < end; i++){
sort(matrix[i].begin(), matrix[i].end());
}
I want to assign that row to a vector to be able to execute the function but I don't know how to do it.
I would also be interested in finding another way to obtain that minimum if this transformation cannot be done.
Is there an efficient way to find the minimum value of the array with this methodology?
Since the maps order by key and not by value, and your keys are the indices of the array, you have no choice but to perform a linear search. You can't sort, because
map
s can't be reordered, since you break the order relationship that the s itselfmap
tries to protect, hence the compiler error. Also, in case you could (using another data structure), sort only to find the minimum, that's inefficient too. The cost of ordering is always higher than searching one by one. You need to sort when you need the sorted values for more than one thing. So:This is more efficient than using
std::sort
or any other mechanism you can think of. There may be other more efficient solutions but it all depends on why you are representing arrays withmap
s or why you would want to have the elements sorted.You must copy all the elements of your array to a one-dimensional array, as follows:
he
arregloTotal
has all the elements of your arrayFinally, change the std::map to a std::vector of defined size, sacrificing flexibility and space for algorithm convenience.
To get the minimum, apply std::sort() row by row, and then loop through the first column comparing until you get the smallest.
And, to know to which positions (x,y) that minor corresponded, I generated a copy of the original matrix and went through the row corresponding to the minimum, until finding the given value.
In this way, the x is the row number, and the y is the column number.