« Check if given array is sorted or not recursively.

Problem:

Check if given array is sorted or not recursively.

Input Format :

Line 1 : An Integer N i.e. size of array

Line 2 : N integers which are elements of the array, separated by spaces

Output Format :

Print "Array is sorted" if array is sorted else "Array is not sorted"

Constraints :

1 <= N <= 10^3

Sample Input 1:

2 3 6 8 10

Sample Output 1:

Array is sorted

Sample Input 2:

2 3 6 8 5 10

Sample Output 2:

Array is not sorted

Solution:

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14// Here we first check rest of the array and then perform our check
15bool is_sorted2(int arr[], int size)
16{
17    if (size == 0 || size == 1)
18    {
19        return true;
20    }
21
22    bool isSmallerOutput = is_sorted2(arr + 1, size - 1);
23    if (!isSmallerOutput)
24    {
25        return false;
26    }
27
28    if (arr[0] > arr[1])
29    {
30        return false;
31    }
32    else
33    {
34        return true;
35    }
36}
37
38// Here we first perform our check and then check rest of the array
39bool is_sorted(int arr[], int size)
40{
41    if (size == 0 || size == 1)
42    {
43        return true;
44    }
45    if (arr[0] > arr[1])
46    {
47        return false;
48    }
49    return is_sorted(arr + 1, size - 1);
50}
51
52int main()
53{
54    int n;
55    cin >> n;
56
57    int *input = new int[n];
58
59    for (int i = 0; i < n; i++)
60    {
61        cin >> input[i];
62    }
63
64    if (is_sorted(input, n))
65    {
66        cout << "Array is sorted" << endl;
67    }
68    else
69    {
70        cout << "Array is not sorted" << endl;
71    }
72
73    return 0;
74}