How to Check if an 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:

1. Nested Loops: Use two nested loops to compare each element with every subsequent element in the array.

2. Check Order: If any element is found to be greater than a subsequent element, the array is not sorted and the function returns false.

3. 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:

1. Single Loop: Traverse the array starting from the second element.

2. Compare with Predecessor: For each element, check if it is less than its predecessor.

3. Return False: If any element is found to be less than its predecessor, the array is not sorted and the function returns false.

4. 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.