isSorted, what is wrong?

[jvqpDjzh]

What is wrong with this function that tries to control if the array passed as first parameter is sorted?

//this function verifies if an integer array is sorted in a range
//returns false if low and high are not in the range: [0-length[ and low >= high 
//returns false if numbers[i] > numbers[i+1]: if the actual number is higher than the next one
//otherwise returns true
bool isSorted( const int* numbers, const int length, const int low, const int high )
{
	if ( low >= 0 && high < length && low < high ) {
		//if the range is composed by just 2 numbers
		if ( high - low == 1 ) {
			if ( numbers[low] > numbers[high] )
				return false;	
		} else {
			for ( int i = low; i< high - 1; i++ )//EDIT: ERRROOOOORRRR!!!!
				if ( numbers[i] > numbers[i + 1] )
					return false;
		}
	} else
		return false;
	
        return true;
}

[MiiNiPaa]

What is wrong? Is it crashes? Is it not working? if so, give an example on data it fails to provide correct example.

Only mistake I see, on line 13 it should be i < high, because there high is a valid index and it should be checked.

[jvqpDjzh]

Thank you!

[jvqpDjzh]

So I don't need the if for the case where the range has just 2 numbers:

bool isSorted( const int* numbers, const int length, const int low, const int high )
{
	if ( low >= 0 && high < length && low < high ) {
		for ( int i = low; i< high; i++ ) 
			if ( numbers[i] > numbers[i + 1] ) 
				return false;
	} else 
		return false;
	return true;
}

[MiiNiPaa]

You do not need to actually pass so many parameters.
It is enough to pass pointer to the first and to the last (or one-past-the-last to be concise with standard library) element.

After you write implementation for that, look into std::is_sorted function: http://www.cplusplus.com/reference/algorithm/is_sorted/

[jvqpDjzh]

Something like this, but this one doesn't control if the pointers are pointing to the elements of the array:

bool isSorted( int* first, const int* one_past_the_last)

{
	while( first != one_past_the_last ){
		if(*first > *(one_past_the_last-1))

			return false;
		first++;
	}
	return true;
}

[MiiNiPaa]

Your code checking only current and last valid elements. You should do something similar to:

bool isSorted( const int* first, const int* last)
{
    if (first == last) 
        return true;
    while (++first != last) {
            if (*first > *(first - 1))
                return false;
    }
    return true;
}

doesn't control if the pointers are pointing to the elements of the array

And it should not. Your prevous code does not check if array pointer indeed points to the array and if length is valid either.

And after implementing two-pointers variety of isSorted you might be surprised to know that there is standard function is_sorted which works not only on arrays, but on basically anything which supports iterators (raw pointers can be seen as raw arrays iterators)

[jvqpDjzh]

Yes, silly I am, I have to think more when writing!

[jvqpDjzh]

line 6 is:

bool isSorted( int* first, const int* one_past_the_last)
{
	while( ++first != one_past_the_last ){
		if(*first < *(first-1))//not ">"
			return false;
	}
	return true;
}

[MiiNiPaa]

Oh yes, sorry.
Please note that your code is going to loop infinitely if first == one_past_the_last. It can happen when range is calculated by different functions (empty range is still a range and, therefore, valid). So replace != on line 3 with < (I left early return when translating from forward iterator based to pointer based function)

And first parameter should be const int* too.

const int* x; // or int const * x means that x is a mutable pointer to constant element, i.e. you can change pointer itself, but not the value it points to:

x += 1;//legal
*x = 1;//illegal 

int* const x; means that x is constant pointer to mutable element. You cannot make pointer poiint to another variable, but you can change value it points to:

x += 1;//illegal
*x = 1;//legal 

And finally const int* const x; // or int const * const x means that x is a constant pointer to constant element. You cannot change anything. Only read value it points to.

[dhayden]

Is it legal to check a range of one element? It seems to me that a collection of 1 is always sorted. Currently your code says that it is always unsorted.

[MiiNiPaa]

Is it legal to check a range of one element?

Yes it is.

It seems to me that a collection of 1 is always sorted

Yes it is. As is collection of 0 elements

Currently your code says that it is always unsorted.

Nope, while( ++first != one_past_the_last ) (or more correctly while( ++first < one_past_the_last )) will evaluate to false right away, making function to return true.

[jvqpDjzh]

Yes, of course, you right!

Yes, about the pointers, I already known that, but sometimes I still get confused (but not so much by now).

Anyway, thank you! You helped much!

[naraku9333]

From OP

for ( int i = low; i< high - 1; i++ )//EDIT: ERRROOOOORRRR!!!!
				if ( numbers[i] > numbers[i + 1] )
					return false;

Should probably be

for ( int i = 0; i< length - 1; i++ )//EDIT: ERRROOOOORRRR!!!!
				if ( numbers[i] > numbers[i + 1] )
					return false;

[MiiNiPaa]

He does check if numbers in range [low, high] are sorted with check if low and high indices are in array (in range [0, length])

[jvqpDjzh]

@naraku9333 (1951)
What do you mean? The correct function verifies if a range of an array is sorted [low-high], not from 0, the first element of the array.