Approach 3 : Using two pointers
Here is a two pointer approach to check whether the given array is sorted or not . It works by taking two pointers left =0 and right = length -1 .
Every time we compare arr[left] and arr[right] , for ascending we check if arr[left] < arr[right] .
If the condition above is true then we compare the left and its previous , right and its next .
else we directly return false
Here is the code for the above approach :
#include <iostream>
using namespace std;
bool isSorted(int arr[], int n) {
int left = 0, right = n - 1;
while (left < right) {
if (arr[left] > arr[right]) {
return false;
} else {
if (left != 0 && right != n - 1 && (arr[left] < arr[left - 1] || arr[right] > arr[right + 1])) {
return false;
}
}
left++;
right--;
}
return true;
}
int main() {
int arr[] = {20, 20, 45, 89, 89, 90}; // Output: true
int nums[] = {20, 20, 78, 98, 99, 97}; // Output: false
cout << boolalpha << isSorted(arr, 6) << endl;
cout << boolalpha << isSorted(nums, 6) << endl;
return 0;
}
#include <stdio.h>
#include <stdbool.h>
bool isSorted(int arr[], int n) {
int left = 0, right = n - 1;
while (left < right) {
if (arr[left] > arr[right]) {
return false;
} else {
if (left != 0 && right != n - 1 && (arr[left] < arr[left - 1] || arr[right] > arr[right + 1])) {
return false;
}
}
left++;
right--;
}
return true;
}
int main() {
int arr[] = {20, 20, 45, 89, 89, 90}; // Output: true
int nums[] = {20, 20, 78, 98, 99, 97}; // Output: false
printf("%s\n", isSorted(arr, 6) ? "true" : "false");
printf("%s\n", isSorted(nums, 6) ? "true" : "false");
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static boolean isSorted(int arr[])
{
int left = 0, n = arr.length, right = n - 1;
while (left < right) {
if (arr[left] > arr[right]) {
return false;
}
else {
if (left != 0 && right != n - 1
&& (arr[left] < arr[left - 1]
|| arr[right] > arr[right + 1])) {
return false;
}
}
left++;
right--;
}
return true;
}
public static void main(String[] args)
{
int arr[]
= { 20, 20, 45, 89, 89, 90 }; /// Output : true;
int nums[]
= { 20, 20, 78, 98, 99, 97 }; // output False
System.out.println(isSorted(arr));
System.out.println(isSorted(nums));
}
}
def is_sorted(arr):
left, right = 0, len(arr) - 1
while left < right:
if arr[left] > arr[right]:
return False
elif left != 0 and right != len(arr) - 1 and (arr[left] < arr[left - 1] or arr[right] > arr[right + 1]):
return False
left += 1
right -= 1
return True
arr = [20, 20, 45, 89, 89, 90] # Output: True
nums = [20, 20, 78, 98, 99, 97] # Output: False
print(is_sorted(arr))
print(is_sorted(nums))
function isSorted(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
if (arr[left] > arr[right]) {
return false;
} else {
if (left !== 0 && right !== arr.length - 1 && (arr[left] < arr[left - 1] || arr[right] > arr[right + 1])) {
return false;
}
}
left++;
right--;
}
return true;
}
let arr = [20, 20, 45, 89, 89, 90]; // Output: true
let nums = [20, 20, 78, 98, 99, 97]; // Output: false
console.log(isSorted(arr));
console.log(isSorted(nums));
Output :
True
False
Time complexity : O(n/2) which is O(n) linear time.
Space complexity : O(1)
Program to check if an array is sorted or not (Iterative and Recursive)
Given an array of size n, write a program to check if it is sorted in ascending order or not. Equal values are allowed in an array and two consecutive equal values are considered sorted.
Examples:
Input : 20 21 45 89 89 90
Output : Yes
Input : 20 20 45 89 89 90
Output : Yes
Input : 20 20 78 98 99 97
Output : No