Thread: Problem with a program that detects if an array is sorted or not.

This program should detect if an array of values (here 5 values of the user's choice) is sorted and if it's not then it should sort it. The problem is my "detection" function sorts every array and I can't figure out why. The logic looks sound to me. Please help.

Code:

#include <iostream>

using namespace std;

int findSmallestValue (int array [], int size, int index)
{
    int indexSmallest = index;
    for (int i = index + 1; i < size; i++)
    {
        if (array [i] < array [indexSmallest])
        {
            indexSmallest = i;
        }
    }
    return indexSmallest; // finds under what index is the smallest value
}

int swap (int array [], int first_index, int second_index)
{
    int temp = array [first_index];
    array [first_index] = array [second_index];
    array [second_index] = temp;
}

void InsertionSort (int array [], int size)
{
    for (int i = 0; i < size; i++)
    {
        int index = findSmallestValue(array, size, i);
        swap (array, i, index);
    } // This function does the sorting
}

void DisplayArray (int array [], int size)
{ // displays the array nicely
    cout << "{";
    for (int i = 0; i < size; i++)
    {
        if (i != 0)
        {
            cout << ",";
        }
        cout << array [i];
    }
    cout << "} \n";
}

bool IsSorted (int array [], int size)
{ // should detect is an array is sorted or not
    int index;
    for (int i = 0; i < size; i++)
    {
        index = findSmallestValue(array, size, i);
    }
    if (index != 0)
    {
        return false;
    }
    else if (index = 0)
    {
        for (int i = index + 1; i < size; i++)
        {
            index = findSmallestValue(array, size, i);
            if (index = i)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}

int main()
{
    int Values [5];
    cout << "Enter 5 values of your choice: \n";
    for (int i = 0; i < 5; i++)
    {
        cin >> Values [i];
    }
    cout << "Your array looks like this: ";
    DisplayArray(Values, 5);
    if (IsSorted(Values, 5))
    {
        cout << "Your array is already nicely sorted. \n";
    }
    else
    {
        cout << "Your array isn't sorted, let me help you: \n";
        InsertionSort(Values, 5);
        DisplayArray (Values, 5);
    }
}

Thank you for your answer, I took your advice and made one loop without calling the function findSmallest, just making sure the condition of the next element being smaller is respected. It works like a charm. I was overcomplicating, thanks a lot

I don't know if this is helpful or not but for future reference there's also the is_sorted function.

Thank you for your answer but seeing as how I'm a beginner at this, I'm trying to work out the code by myself to better my skills and understanding

Fair enough. You know something is sorted if for ever iteration, the next element is equal to or greater than the current.

Code:

template <typename InputIterator>
auto is_sorted(InputIterator const begin, InputIterator const end) -> bool
{
  for (; begin != end; ++begin) {
    auto const tmp = begin;
    auto const next_val = *(++tmp);

    auto const curr_val = *begin;
    if (curr_val > next_val) {
      return false;
    }
  }

  return true;
}

This isn't tested but I think it should work. Note, it really just relies on duck typing so if you pass it the wrong thing, the error messages aren't that great.

If you really want it to work with input iterators, wouldn't it have to be more like this?

Code:

#include <iostream>
#include <iterator>

template <typename InputIterator>
bool is_sorted(InputIterator begin, InputIterator end) {
    if (begin == end) return true;
    auto prev_val = *begin;
    for (++begin; begin != end; ++begin) {
        auto curr_val = *begin;
        if (prev_val > curr_val)
            return false;
        prev_val = curr_val;
    }
    return true;
}

int main() {
    std::istream_iterator<int> is_it(std::cin), is_end;
    std::cout<< is_sorted(is_it, is_end)<< '\n';
}

The point is that every time you dereference the iterator it reads another value from the associated input stream.

First, good catch on the 0-length case! I've actually never messed much with `istream_iterator` struff. I tried messing with it in the cpp.sh shell but for some reason it doesn't like me trying to send the EOF signal (kept bookmarking it in chrome lol). Was my code not working for your particular instance? To me they look largely logically equivalent.

Also, how cool is this? We refactored software together and we wound up making it better!

Originally Posted by MutantJohn

Was my code not working for your particular instance? To me they look largely logically equivalent.

The difference is that you read two values from the stream every iteration (*curr reads a value and *next reads a value). So when I run your program on the following file, it says it's in order since each pair of numbers is in order.

Code:

6
7
4
5
8
9
1
2

I don't know whether *curr is guaranteed to happen before *next in the expression *curr > *next (anybody?), but either way it's a problem.

I've actually never messed much with `istream_iterator` stuff. ... Also, how cool is this? We refactored software together and we wound up making it better!

I'm no expert either, that's for sure! I've definitely learned something with this back-and-forth coding exercise.

I _knew_ there were iterator concepts!

Also, my bad. I didn't even realize that the "real" is_sorted was written for ForwardIterator.