Program to check if an array is sorted or not (Iterative and Recursive) in C

Given an array arr[] with n number of elements, our task is to check whether the given array is in sorted order or not, If it is in sorted order then print “The array is in sorted order”, else print “The array is not in sorted order”.

To solve the above stated problem we can use Iterative or Recursive approach, we will be discussing both.

Recursive Approach

So, what is a Recursive approach? In Recursive approach we recursively call a function again and again until we get the desirable result. In recursive approach the values returned by function is stored in stack memory.

Input 

arr[] = {12, 13, 14, 16, 18}

Output 

The array is in sorted order

Explanation − 12 < 13 < 14 < 16 < 18, so, yes the array is in sorted

Input 

arr[] = {2, 1, 3, 5, 6}

Output 

The array is not in sorted order

Explanation − 2 not smaller than 1, so, it is not in the sorted order.

Approach used below is as follows to solve the problem −

• Take an array arr[] as an input and initialize n with the size of an array.

• Check if we reached the starting of an array, return true.

• Check if the previous element of an array is not smaller than the next element, return false.

• Decrement n and goto step 2.

Algorithm

Start In function int arraySortedCheck(int arr[], int n)    Step 1→ If n == 1 || n == 0 then,       Return 1    Step 2→ If arr[n-1] < arr[n-2] then,       Return 0    Step 3→ Return arraySortedCheck(arr, n-1) In Function int main(int argc, char const *argv[])    Step 1→ Declare and initialize arr[] as {1,8,3,4,7}    Step 2→ Declare and initialize int n as sizeof(arr)/sizeof(arr[0])    Step 3→ If arraySortedCheck(arr, n) then,       Print "Array is in sorted order”    Step 4→ Else       Print "Array is not in sorted order” Stop

Example

 Live Demo

//Recursive approach #include <stdio.h> //Recursive function to check if it //is in sorted order or not int arraySortedCheck(int arr[], int n){    //all elements are checked and    //all are in sorted order    if (n == 1 || n == 0)       return 1;    //when an array is not in sorted order    if(arr[n-1] < arr[n-2])       return 0;    return arraySortedCheck(arr, n-1); } int main(int argc, char const *argv[]){    int arr[] = {1,8,3,4,7};    int n = sizeof(arr)/sizeof(arr[0]);    if(arraySortedCheck(arr, n)){       printf("Array is in sorted order
");    }    else       printf("Array is not in sorted order
");    return 0; }

Output

If run the above code it will generate the following output −

Array is in sorted order

Iterative Approach

In iterative approach, we use loops like for-loop, while-loop or do-while loop which executes the statements till the condition holds true which means 1.

Input 

arr[] = {12, 13, 14, 16, 18}

Output 

The array is in sorted order

Explanation − 12 < 13 < 14 < 16 < 18, so, yes the array is in sorted order

Input 

arr[] = {2, 1, 3, 5, 6}

Output 

The array is not in sorted order

Explanation 2 not smaller than 1, so, it is not in the sorted order.

Approach used below is as follows to solve the problem

• Take an input arr[].

• Loop until we reach the end of that array.

  • Check if the current element is not smaller than the next element, return false and exit.

  • Else continue.

• Goto step 2.

Algorithm

Start In function int arraySortedCheck(int arr[], int n)    Step 1 → Loop For i = 0 and i < n and ++i       If arr[n-1] < arr[n-2] then,          Return 0    Step 2→ Return 1 In Function int main(int argc, char const *argv[])    Step 1→ Declare and initialize arr[] as {1,8,3,4,7}    Step 2→ Declare and initialize int n as sizeof(arr)/sizeof(arr[0])    Step 3→ If arraySortedCheck(arr, n) then,       Print "Array is in sorted order”    Step 4→ Else       Print "Array is not in sorted order” Stop

Example

 Live Demo

//Iterative approach #include <stdio.h> int arraySortedCheck(int arr[], int n){    for (int i = 0; i < n; ++i){       //when an array is not in sorted order       if(arr[n-1] < arr[n-2])          return 0;    }    //all elements are checked and    //all are in sorted order    return 1; } int main(int argc, char const *argv[]){    int arr[] = {1,8,3,4,7};    int n = sizeof(arr)/sizeof(arr[0]);    if(arraySortedCheck(arr, n)){       printf("Array is in sorted order
");    }    else       printf("Array is not in sorted order
");    return 0; }

Output

If run the above code it will generate the following output −

Array is in sorted order