struct Pair
{
int min;
int max;
};
struct Pair getMinMax(int arr[], int n)
{
struct Pair minmax;
int i;
// If array has even number of elements
// then initialize the first two elements
// as minimum and maximum
if (n % 2 == 0)
{
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.min = arr[0];
minmax.max = arr[1];
}
// Set the starting index for loop
i = 2;
}
// If array has odd number of elements
// then initialize the first element as
// minimum and maximum
else
{
minmax.min = arr[0];
minmax.max = arr[0];
// Set the starting index for loop
i = 1;
}
// In the while loop, pick elements in
// pair and compare the pair with max
// and min so far
while (i < n - 1)
{
if (arr[i] > arr[i 1])
{
if(arr[i] > minmax.max)
minmax.max = arr[i];
if(arr[i 1] < minmax.min)
minmax.min = arr[i 1];
}
else
{
if (arr[i 1] > minmax.max)
minmax.max = arr[i 1];
if (arr[i] < minmax.min)
minmax.min = arr[i];
}
// Increment the index by 2 as
// two elements are processed in loop
i = 2;
}
return minmax;
}
// Driver code
int main()
{
int arr[] = { 1000, 11, 445,
1, 330, 3000 };
int arr_size = 6;
Pair minmax = getMinMax(arr, arr_size);
cout << "nMinimum element is "
<< minmax.min << endl;
cout << "nMaximum element is "
<< minmax.max;
return 0;
}
In this qsn we have to return max and min value simultaneously so here struct is made. I copied this code from GEEKSFORGEEKS site. I was trying this code's approach but stuck in doubt that how here comparisons is being calculates. In this code i want to know that how comparisons is 3*(n-1)/2 when n=odd?
CodePudding user response：
The above code is the definition of premature optimization. Where you literally are taking the below code that takes 4 int compares per two elements, down to 3, and the cost of making the code hard to read, and easier to write bugs into.
Even in the code written below these could be changed to if() else if(), since they are populated with the same value to start with, both conditions are impossible to be true. But it's not worth making that change to make the reader have to think through if that is actually true.
Trying to be too smart, and you'll only outsmart yourself.
struct Pair
{
int min;
int max;
};
Pair getMinMax(int arr[], int length){
Pair output = {0, 0};
if(length < 1){
return output;
}
output.min = arr[0];
output.max = arr[0];
for(int i= 1; i < length; i ){
if(arr[i] < output.min){
output.min = arr[i];
}
if(arr[i] > output.max){
output.max = arr[i];
}
}
return output;
}
int main()
{
int array[] = { 8, 6, 4, 2, 9, 4};
auto data = getMinMax(array, 6);
std::cout << data.min << " " << data.max;
}
CodePudding user response：
Solution using STL code (C 20) :
#include <algorithm>
#include <vector>
#include <iostream>
struct MinMaxResult
{
int min;
int max;
};
MinMaxResult getMinMax(const std::vector<int>& values)
{
return (values.size() == 0) ?
MinMaxResult{} :
MinMaxResult(std::ranges::min(values), std::ranges::max(values));
}
int main()
{
std::vector<int> values{ 8, 6, 4, 2, 9, 4 };
auto data = getMinMax(values);
std::cout << data.min << ", " << data.max;
return 0;
}
CodePudding user response：
There are answers (good ones imho), but so far none does actually count the number of comparisons. With std::minmax_element you can count the number of comparisons like this:
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
template <typename TAG>
struct compare {
static size_t count;
template <typename T>
bool operator()(const T& a,const T& b){
count;
return a < b;
}
};
template <typename TAG> size_t compare<TAG>::count = 0;
template <typename TAG>
compare<TAG> make_tagged_compare(TAG) { return {};}
int main()
{
std::vector<int> x{1,2,3};
auto c = make_tagged_compare([](){});
auto mm = std::minmax_element(x.begin(),x.end(),c);
std::cout << *mm.first << " " << *mm.second << " " << c.count;
}
Standard algorithms may copy predicates passed to them, hence count is static. Because I want to reuse compare later to count a different algorithm, I tagged it (each lambda expression is of different type, hence it can be used as unique tag). The output is:
1 3 3
It correctly finds min and max, 1 and 3, and needs 3 comparisons to achieve that.
Now if you want to compare this to a different algorithm, it will look very similar to the above. You pass a functor that compares elements and counts the number of comparisons of the algorithm. As example I use a skeleton implementation that does only a single comparison and either returns {x[0],x[1]} or {x[1],x[0]}:
template <typename IT, typename Compare>
auto dummy_minmax(IT first, IT last,Compare c) {
auto second = first 1;
if (c(*first,*second)) return std::pair(*first,*second);
else return std::pair(*second,*first);
}
int main()
{
std::vector<int> x{1,2,3};
auto c = make_tagged_compare([](){});
auto mm = std::minmax_element(x.begin(),x.end(),c);
std::cout << *mm.first << " " << *mm.second << " " << c.count << "\n";
double x2[] = {1.0,2.0,5.0};
auto c2 = make_tagged_compare([](){});
auto mm2 = dummy_minmax(std::begin(x2),std::end(x2),c2);
std::cout << mm2.first << " " << mm2.second << " " << c2.count;
}