Check if Array is Sorted

There are many times we need to check if an array is sorted or not. Checking if an array is sorted can be approached in multiple ways. Here, we we'll discuss two solutions: a brute force approach and an optimal approach.

Solution 1: Brute Force Approach

This method involves comparing each element with every other element that comes after it in the array to ensure that the array is sorted in non-decreasing order.

Implementation:

// Solution-1: Brute Force Approach
// Time Complexity: O(n*n)
// Space Complexity: O(1)
bool isArraySorted(vector<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;
}

Logic:

Nested Loops: Use two nested loops to compare each element with every subsequent element in the array.
Check Order: If any element is found to be greater than a subsequent element, the array is not sorted and the function returns false.
Return True: If no such pair is found, the array is sorted and the function returns true.

Time Complexity: O(n²)

Explanation: The outer loop runs n times and for each iteration, the inner loop runs up to n-1 times, resulting in a quadratic time complexity.

Space Complexity: O(1)

Explanation: The algorithm uses a constant amount of extra space.

Example:

Input: arr = [10, 20, 30, 40, 50], n = 5
Output: true
Explanation: All elements are in non-decreasing order.

Solution 2: Optimal Approach

A more efficient method involves a single pass through the array, comparing each element with its predecessor to ensure that the array is sorted.

Implementation:

// Solution-2: Optimal Approach
// Time Complexity: O(n)
// Space Complexity: O(1)
bool isArraySorted(vector<int> &arr, int n)
{
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[i - 1])
        {
            return false;
        }
    }
    return true;
}

Logic:

Single Loop: Traverse the array starting from the second element.
Compare with Predecessor: For each element, check if it is less than its predecessor.
Return False: If any element is found to be less than its predecessor, the array is not sorted and the function returns false.
Return True: If no such element is found, the array is sorted and the function returns true.

Time Complexity: O(n)

Explanation: The algorithm makes a single pass through the array, resulting in linear time complexity.

Space Complexity: O(1)

Explanation: The algorithm uses a constant amount of extra space.

Example:

Input: arr = [10, 20, 30, 40, 50], n = 5
Output: true
Explanation: All elements are in non-decreasing order.

Comparison

Brute Force Method:
- Pros: Simple and easy to understand.
- Cons: Inefficient due to its O(n²) time complexity.
- Use Case: Not suitable for large arrays due to its inefficiency.
Optimal Method:
- Pros: Highly efficient with O(n) time complexity.
- Cons: None significant.
- Use Case: Ideal for checking the sorted status of large arrays.

Edge Cases

Empty Array: An empty array is considered sorted.
Single Element Array: An array with a single element is considered sorted.
Array with All Identical Elements: An array where all elements are the same is considered sorted.

Additional Notes

Efficiency: The optimal approach is significantly more efficient for large datasets.
Simplicity: Despite its efficiency, the optimal approach is also simple to implement.
Practicality: The optimal method is generally preferred due to its linear time complexity and constant space complexity.

Conclusion

Checking if an array is sorted can be done efficiently using a single-pass approach. While the brute force method provides a simple but inefficient solution, the optimal method is both efficient and easy to implement, making it suitable for large datasets.

How to Check if an Array is Sorted

Comments

Array

How to Find the Second Largest Element in an Array

More from this blog

How to Find the Element that Appears Once in an Array

How to Find the Maximum Consecutive Ones in an Array

How to Find the Missing Number in an Array

Intersection of Two Sorted Arrays

Union of Two Sorted Arrays

Solution 1: Brute Force Approach

Solution 2: Optimal Approach

Comparison

Edge Cases

Additional Notes

Conclusion

Command Palette

Comments

Array

How to Find the Second Largest Element in an Array

More from this blog

Solution 1: Brute Force Approach

Solution 2: Optimal Approach

Comparison

Edge Cases

Additional Notes

Conclusion