.png)
Check if an Array is Sorted
Problem Statement
Given an array of elements, the task is to check whether the array is sorted or not.
An array is considered sorted if:
- The elements are in non-decreasing order (ascending), or
- The elements are in non-increasing order (descending)
In this problem, we will check for ascending order sorting.
Why This Problem Is Important
This problem is crucial because:
- Many algorithms (binary search, two-pointer technique) require sorted arrays
- It helps validate input before applying optimized algorithms
- It tests logical comparison and traversal skills
- It is commonly asked in interviews as a foundation problem
Understanding this problem helps prevent logical errors when working with sorted-based techniques.
Input and Output Format
Input
Array: [10, 20, 30, 40, 50]
Output
Array is sorted
Input
Array: [10, 30, 20, 40]
Output
Array is not sorted
Key Concept
- Traverse the array from left to right
- Compare each element with the next element
- If any element is greater than the next one, the array is not sorted
Step-by-Step Algorithm
- Traverse the array from index 0 to n-2
- Compare arr[i] with arr[i+1]
- If arr[i] > arr[i+1], return not sorted
- If traversal completes without violation, return sorted
Pseudocode
for i from 0 to n-2:
if arr[i] > arr[i+1]:
return false
return true
Dry Run Example
Array: [10, 20, 30, 40]
Compare 10 ≤ 20 → OK
Compare 20 ≤ 30 → OK
Compare 30 ≤ 40 → OK
Array is sorted
Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Language-wise Implementation
C Implementation
#include
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int isSorted = 1;
for(int i = 0; i < n - 1; i++) {
if(arr[i] > arr[i + 1]) {
isSorted = 0;
break;
}
}
if(isSorted)
printf("Array is sorted");
else
printf("Array is not sorted");
return 0;
}
Output
Array is sorted
C++ Implementation
#include
using namespace std;
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
bool isSorted = true;
for(int i = 0; i < n - 1; i++) {
if(arr[i] > arr[i + 1]) {
isSorted = false;
break;
}
}
if(isSorted)
cout << "Array is sorted";
else
cout << "Array is not sorted";
return 0;
}
Output
Array is sorted
Java Implementation
public class Main {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
boolean isSorted = true;
for(int i = 0; i < arr.length - 1; i++) {
if(arr[i] > arr[i + 1]) {
isSorted = false;
break;
}
}
if(isSorted)
System.out.println("Array is sorted");
else
System.out.println("Array is not sorted");
}
}
Output
Array is sorted
Python Implementation
arr = [10, 20, 30, 40, 50]
is_sorted = True
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
is_sorted = False
break
if is_sorted:
print("Array is sorted")
else:
print("Array is not sorted")
Output
Array is sorted
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {10, 20, 30, 40, 50};
bool isSorted = true;
for(int i = 0; i < arr.Length - 1; i++) {
if(arr[i] > arr[i + 1]) {
isSorted = false;
break;
}
}
if(isSorted)
Console.WriteLine("Array is sorted");
else
Console.WriteLine("Array is not sorted");
}
}
Output
Array is sorted
JavaScript Implementation
let arr = [10, 20, 30, 40, 50];
let isSorted = true;
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
isSorted = false;
break;
}
}
console.log(isSorted ? "Array is sorted" : "Array is not sorted");
Output
Array is sorted
Common Mistakes
- Comparing wrong indices
- Running loop till n instead of n-1
- Confusing sorted with strictly increasing
- Ignoring duplicate values
Summary
Checking whether an array is sorted is a fundamental validation step that ensures correctness before applying optimized algorithms like binary search or two-pointer techniques. By comparing each element with its next neighbor, we can efficiently verify sorted order in linear time without additional memory. This problem strengthens logical reasoning, loop control, and index management, all of which are essential skills for tackling more advanced data structure challenges.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
