Traversals - 2
As it is probably clear from the previous article, we'll explore some beginner level problems in this section.
Check if sorted
This one isn't very tough in my opinion. As you must've read, we'll be given an array, and we need to check if the array is sorted in a non-decreasing manner or not?
What does non-decreasing order mean?
It means that the inequality a[0] <= a[1] <="a[2]" ... a[n-3] should hold true. p>
In other terms, it means that the 2nd element should be greater than or equal to the 1st element, the 3rd element should be greater than or equal to the 2nd element, the 4th element should be greater than or equal to the 3rd element, and so on...
How to solve?
Now, to check whether the given array is sorted or not, we can check exactly what the definition says.
Explaining the idea
So, we'll just iterate over the array and while iterating, the inequality a[i] <= a[i+1]< i> should be true for all valid i.
So, if a[i] > a[i+1] for even 1 value of i, then we'll return false, i.e. the array is not sorted. Otherwise, after we've checked for all the valid i and everything is fine, we'll return true. Hope it makes sense.
Implementation
bool arraySortedOrNot(int arr[], int n) {
for(int i = 0; i < n; ++i) {
if(arr[i] > arr[i+1])
return false;
}
return true;
}Spoiler (read the implementation carefully before you continue)
The thing is that there is a small mistake in the implementation, again.Go back and try to find it before opening this up.
Cool, now that you're here, I'll disclose it.
The thing is, the for loop should go until i < n - 1 and not until i < n. Try to think why, before reading further.
Okay, so the reason is that when i = n - 1, the code will end up comparing arr[n-1] and arr[n], which doesn't make sense because arr[n] is not part of the array, and will probably contain a garbage value.
Implementation 2
Now, the implementation given below is the correct one, I promise.bool arraySortedOrNot(int arr[], int n) {
for(int i = 0; i < n - 1; ++i) {
if(arr[i] > arr[i+1])
return false;
}
return true;
}A confession
By now, you must've guessed that I have a habit of making a small mistake first, urging you to try to find it, and then making it right. It'll happen in the future as well, won't apologise for it. xD