C++ finding the extreme points of an algorithm

Question

The question: Let A be an array of n elements (that is, the elements of A are A[0], ..., A[n−1]). An element A[i] is extreme if the following conditions hold regarding A[i]:

• A[i] is not the first nor the last element of A. That is, 0 < i < n–1 and either A[i−1] < A[i] > A[i+1] or A[i−1] > A[i] < A[i+1]. For example, the extreme points of an array [0, 5, 3, 6, 8, 7, 15, 9] are 5, 3, 8, 7, 15.

Write an algorithm that prints the extreme points of the given array. If there are no extreme points, the algorithm prints “SORTED”. Do you agree that an array has no extreme points if and only if it is sorted? Explain your answer.

What I have managed to do:

#include <iostream>
using namespace std;

bool extremePoint(int arr[], int n, int num, int leftNeighbour, int rightNeighbour);

int main()
{
    int array[] = { 0, 5, 3, 6, 8, 7, 15, 9 };
    int size = sizeof(array) / sizeof(array[0]);

    for (int i = 1; i < size - 1; i++) {

        // If the current element is a peak 
        if (extremePoint(array, size, array[i], array[i - 1], array[i + 1]))
        {
            cout << array[i] << " ";
        }
    }

    return 0;
}

bool extremePoint(int arr[], int size, int num, int leftNeighbour, int rightNeighbour)
{
    if (num > leftNeighbour && num > rightNeighbour)
    {
        return true;
    }

    if (num < leftNeighbour && num < rightNeighbour)
    {
        return true;
    }
    else
    {
        return false;
    }
}

The problem:

I have managed to write the algorithm that prints the extreme points of the given array.

Can anyone please help me with this part:

If there are no extreme points, the algorithm prints “SORTED”. Do you agree that an array has no extreme points if and only if it is sorted? Explain your answer.

Answer 1

For starters this function

bool extremePoint(int arr[], int size, int num, int leftNeighbour, int rightNeighbour)
{
    if (num > leftNeighbour && num > rightNeighbour)
    {
        return true;
    }

    if (num < leftNeighbour && num < rightNeighbour)
    {
        return true;
    }
    else
    {
        return false;
    }
}

does not use its parameters arr and size.

The function can be written like

bool extremePoint( int num, int  eftNeighbour, int rightNeighbour )
{
    return leftNeighbour < num && rightNeighbour < num ||
           num < leftNeighbour && num < rightNeighbour;
}

If a sequence does not contain an extreme point it does not mean that the sequence is sorted.

For example, consider the sequence

1, 2, 2, 1

On the other hand, it is obvious that a sorted sequence indeed does not have an extreme point.

Pay attention tp that this phrase

Write an algorithm that prints the extreme points of the given array.

can be interpreted as a requirement to write a separate function (algorithm).

I would write such an algorithm the following way as it is shown in the demonstrative program below

#include <iostream>
#include <iterator>

template <typename InputIterator, typename OutputIterator>
OutputIterator extreme_points( InputIterator first, 
                               InputIterator last,
                               OutputIterator out )
{
    if ( first != last )
    {
        for ( auto prev_value = *first++; first != last; )
        {
            auto current_value = *first;
            if ( ++first != last )
            {
                if ( prev_value < current_value && *first < current_value ||
                     current_value < prev_value && current_value < *first )
                {
                    *out++ = current_value;
                }
                
                prev_value = current_value;
            }
        }
    }
    
    return out;
}

int main() 
{
    int a[] = { 0, 5, 3, 6, 8, 7, 15, 9 };

    extreme_points( std::begin( a ), 
                    std::end( a ), 
                    std::ostream_iterator<int>( std::cout, ", " ) );
                    
    std::cout << '\n';
    
    
    return 0;
}

The program output is

5, 3, 8, 7, 15,