Problem Statement
Given an array of size n, write a program to check if the given array is sorted in (ascending/ Increasing/ Non-decreasing) order or not. If the array is sorted then return True, else return false.
Note: Two consecutive equal values are considered to be sorted.
Example 1:
Input: N = 5, arr[] = {4, 5, 6, 7, 8}
Output: True
Example 2:
Input: N = 5, arr[] = {10, 5, 6, 6, 8}
Output: False
Different Approaches
1 Brute Force Approach
Iterate through the array and compare each element with its adjacent element. If any element is found to be smaller than its previous element, conclude that array is not sorted.
Code:
#include <bits/stdc++.h>
using namespace std;
bool isSorted(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i])
return false;
}
}
return true;
}
int main() {
int arr[] = {1, 2, 3, 4, 5}, n = 5;
bool ans = isSorted(arr, n);
if (ans) cout << "True" << endl;
else cout << "False" << endl;
return 0;
}
Complexity Analysis:
Time Complexity: O(N^2)
Space Complexity: O(1)
2 Optimal Approach: Efficient (Single traversal)
This approach is essentially a simplified version of the iterative method where you iteratively check if each element is greater than or equal to its previous element.
Algorithm:
- Iterate through the array.
- For each element, compare it with its previous element.
- If the previous element is smaller than or equal to the current element, continue to the next element.
- If any element violates the condition (i.e., previous element is greater than the current element), return false immediately, indicating that the array is not sorted.
- If the loop completes successfully without encountering any violation, return true, indicating that the array is sorted.
Code:
#include <iostream>
using namespace std;
bool isArraySorted(int arr[], int size) {
for (int i = 1; i < size; ++i) {
if (arr[i] < arr[i - 1])
return false;
}
return true;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int size = sizeof(arr) / sizeof(arr[0]);
if (isArraySorted(arr, size))
cout << "Array is sorted in ascending order";
else
cout << "Array is not sorted in ascending order";
return 0;
}
Complexity Analysis
Time Complexity: The time complexity of the approach is O(n)
, where n is the size of the array.
Space Complexity: The space complexity of the approach is O(1)
because it uses only a constant amount of extra space for variables, regardless of the size of the input array.