DEV Community

Cover image for How to Check if an Array is Sorted
Mahbub Alam Masum
Mahbub Alam Masum

Posted on • Originally published at blog.masum.dev

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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.


AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay