How to check if an Array is Sorted in C++

In this article, we will discuss different ways to check if an array is sorted or not in C++.

Table Of Contents

Problem Description

We have given an array that contains n numbers of elements. Now, we have to check whether the array elements are in sorted order or not.

Here we assume sorted order as ascending order.

• If the given array was sorted, we have to print The Array is in sorted order.
• If the given array was not sorted, we have to print The Array is not in sorted order.

We can think of solving the given problem in four ways. Let’s understand all the approaches in details one by one.

Check if array is sorted using std::adjacent_find()

The very first approach that we are going to learn is using the standard library algorithm std::adjacent_find(). It accepts a range and a comparison function, is used to verify if an array is sorted. You can send an iterator to the beginning and end of an array in C++11. The default comparison operator can be used to check for a sorted array in ascending order as shown below.

• Time Complexity is of an order of n, means linear. Basically it itrates over the range between first and last, and compares pairs of elements until a mismatch is identified. Time Complexity O(n).
• Space Complexity is also of order n means linear. Space Complexity O(n).

Code Using std::adjacent_find()

// Using std::adjacent_find() to check whether an Array is sorted or not
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int arr[] = {1,2,3,4,5};

   // Iterating from beginning of the array to end of the array,
   // till we get a decreasing element.
   // If decreasing element is not found that means array is sorted
   // and function return the iterator value of end of array.
   // greater<int>() it is deafult comparison operator

    bool isArraySorted = (end(arr) == adjacent_find( begin(arr),
                                                     end(arr),
                                                     greater<int>()));

    if(isArraySorted) 
    {
      cout << "The Array is in sorted order.\n";
    }
    else
    {
       cout << "The Array is not in sorted order.\n";
    }
    return 0;
}

Output

The Array is in sorted order.

Check if array is sorted using std::is_sorted()

The second approach that we are going to learn is the standard library algorithm std::is_sorted ( ). It accepts a range and a comparison function and, is used to verify if an array is sorted or not. You can send an iterator to the beginning and end of an array in C++11. The default comparison operator can be used to check for a sorted array in ascending order as shown below.

• Time Complexity is of an order of n means linear. Basically it is the range between first and last, it compares pairs of elements until a mismatch is identified. Time Complexity O(n).
• Space Complexity is also of order n means linear. Space Complexity O(n).

Code Using std::is_sorted()

// Using std::is_sorted() to check whether an Array is sorted or not
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {1,2,3,4,5};

    bool isArraySorted = is_sorted(begin(arr), end(arr));

    if(isArraySorted) 
    {
      cout << "The Array is in sorted order.\n";
    }
    else{
       cout << "The Array is not in sorted order.\n";
    }
    return 0;
}

Output

The Array is in sorted order.

Check if array is sorted using Recursive Approach

As we already know that in Recursion, first we decide the base case. So the base case for our problem is when the array has zero or one element.

Following are the steps involved in this approach.

1. Print The Array is in sorted order when the size of array becomes zero or one.
2. Now check the last two elements of the array.
3. If the last two elements are in ascending order(sorted order), then again, make a recursive call with the previous element, which is the (n-1)th element.
4. Suppose it returns true, then continues to the 3rd step. Else return false, which signifies that the array was not in sorted order.
5. If all the array elements were sorted, then the Recursion will go to step 1.

• Time Complexity is of an order of n means linear Time Complexity O(n).

• Space Complexity is also of order n means linear Space Complexity O(n).

Code for Recursion Based Approach

// Recursion based approach to check whether an Array is sorted or not

#include<iostream>

using namespace std;

// Function to check whether an array is sorted or not
int IsarraySorted(int arr[],int n)
{
    // Base Case 
    if(n==0 || n==1)
    {
        return 1;
    }

    // Check last two element
    if(arr[n-1]<arr[n-2])
    {
        return 0;
    }

    // keep on checking previous element
    return IsarraySorted(arr,n-1);
}


int main()
{
     int arr[] = { 1,2,3,4,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    if (IsarraySorted(arr, n))
        cout << "The Array is in sorted order.\n";
    else
        cout << "The Array is not in sorted order.\n";

    return 0;    
}

Output

The Array is in sorted order.

Check if array is sorted using Iterative Approach

The advantage of using the Iterative approach is that it takes O(1) space complexity, because it avoids the usage of stack space used in the recursion method.

Following are the steps involved in this approach.

Print The Array is in sorted order when the size of array becomes zero or one.

1. Start loop from the first element.
2. Compare the previous element with the current element.
3. If these two element are sorted, then move to the next element.
4. Otherwise return false, which signifies that the array was not in sorted order.
5. If all the array elements were in sorted order, then the loop comes to the end of the array.

• Time Complexity is of order of n means linear Time Complexity O(n).

• Space Complexity is of constant order means Space Complexity O(1).

Code for Iterative Based Approach

// Iteration based approach to check whether an Array is sorted or not

#include<iostream>

using namespace std;

// Function to check whether an array is sorted or not
int IsarraySorted(int arr[],int n)
{
    // Checking that array has zero or one element 
    if(n==0 || n==1)
    {
        return 1;
    }

    // Start loop from the first element and goes until the condition get true or loop comes to the end of array

    // Compare the previous element with the current element.

   for(int i=1;i<n;i++)
   {
     if(arr[i-1]>arr[i])
     {
         return false;
     }
   }

   // loops comes to end as the array was in sorted order
     return true;
}


int main()
{
    int arr[] = { 1,2,3,4,5 };
    int n = sizeof(arr) / sizeof(arr[0]);


    if (IsarraySorted(arr, n))
        cout << "The Array is in sorted order.\n";
    else
        cout << "The Array is not in sorted order.\n";

    return 0;    
}

Output

The Array is in sorted order.

Summary

We have seen the detailed explanation of four approaches to check whether the array is in sorted order or not. The first one is using the std::adjacent_find(), second is using the std::is_sorted(), third one is the Recursion based approach, and the last one is using the Iteration based approach. Also, we have seen the Time and Space Complexity of all the four approaches.