Check if a given array is pairwise sorted or not
The problem at hand revolves around checking whether a given array is pairwise sorted or not. Pairwise sorting implies that the array is sorted in such a way that each pair of adjacent elements is in ascending order. In simpler terms, the first two elements should be in increasing order, the next two elements should be in increasing order, and so on.
Problem Statement
Given an array, we need to determine whether it is pairwise sorted or not. If the array is pairwise sorted, we output "Yes", otherwise, we output "No". Additionally, if the length of the array is odd, we'll print a message stating that "Pair lengths are Odd".
Example
Let's illustrate this with two arrays:
-
arr1[] = {1, 2, 5, 7, 2, 5, 7, 9, 10, 14}
- The array length is even.
- Pairs: (1, 2), (5, 7), (2, 5), (7, 9), (10, 14)
- Each pair is sorted in ascending order.
- Output: "Yes"
-
arr2[] = {6, 7, 4, 6, 9, 5, 2, 1}
- The array length is even.
- Pairs: (6, 7), (4, 6), (9, 5), (2, 1)
- Not all pairs are sorted in ascending order.
- Output: "No"
Idea to Solve
We can solve this problem by iterating through the array in steps of two, comparing each pair of adjacent elements. If we find a pair where the first element is greater than the second element, then the array is not pairwise sorted. Otherwise, if all pairs are sorted, the array is pairwise sorted.
Pseudocode
function is_pairwise_sorted(arr, size):
if size <= 1:
return
else if size % 2 != 0:
print "Pair lengths are Odd"
else:
status = 1
for i from 0 to size - 2 by 2:
if arr[i] > arr[i+1]:
status = 0
break
print_data(arr, size)
if status == 1:
print "Yes"
else:
print "No"
function print_data(arr, size):
for i from 0 to size - 1:
print arr[i]
arr1 = [1, 2, 5, 7, 2, 5, 7, 9, 10, 14]
is_pairwise_sorted(arr1, size_of(arr1))
arr2 = [6, 7, 4, 6, 9, 5, 2, 1]
is_pairwise_sorted(arr2, size_of(arr2))
Algorithm Explanation
- The
is_pairwise_sorted
function takes an arrayarr
and its sizesize
as input. - It checks if the size is less than or equal to 1. If so, it returns since an array of size 1 or less is always pairwise sorted.
- If the size is odd, it prints a message about odd pair lengths.
- Otherwise, it initializes the
status
variable to 1, assuming the array is pairwise sorted. - It iterates through the array with a step of 2, comparing adjacent pairs.
- If it finds a pair where the first element is greater than the second element, it sets
status
to 0 and breaks out of the loop. - After the loop, it prints the array elements using the
print_data
function. - Depending on the
status
, it prints either "Yes" or "No". - The
print_data
function simply prints each element of the array.
Code Solution
//C Program
//Check if a given array is pairwise sorted or not
#include <stdio.h>
//Print array elements
void print_data(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
}
//Check whether given array is form of pairwise sorted or not
void is_sorted_pair(int arr[],int size)
{
if(size<=1)
{
return;
}
else if(size%2!=0)
{
//When array size is odd
printf("Pair length are Odd\n");
}
else{
int status = 1;
for (int i = 0; i < size-1; i+=2)
{
if(arr[i] > arr[i+1])
{
//When pair is not sorted
status=0;
break;
}
}
//Display array data
print_data(arr,size);
if(status==1)
{
printf("\n Yes\n");
}
else
{
printf("\n No\n");
}
}
}
int main()
{
//Test Case
//Define array elements
int arr1[] ={1,2,5,7,2,5,7,9,10,14};
//Get the length of array
int size=sizeof(arr1) / sizeof(arr1[0]);
is_sorted_pair(arr1,size);
//Define array elements
int arr2[] ={6,7,4,6,9,5,2,1};
//Get the length of array
size=sizeof(arr2) / sizeof(arr2[0]);
is_sorted_pair(arr2,size);
return 0;
}
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
/*
C++ Program
Check if a given array is pairwise sorted or not
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Print array elements
void print_data(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
//Check whether given array is form of pairwise sorted or not
void is_sorted_pair(int arr[], int size) {
if (size <= 1) {
return;
} else
if (size % 2 != 0) {
//When array size is odd
cout << "Pair length are Odd\n";
} else {
bool status = true;
for (int i = 0; i < size - 1; i += 2) {
if (arr[i] > arr[i + 1]) {
//When pair is not sorted
status = false;
break;
}
}
//Show array elements
this->print_data(arr, size);
if (status == true) {
cout << "\n Yes\n";
} else {
cout << "\n No\n";
}
}
}
};
int main() {
MyArray obj ;
//Test Case
//Define array elements
int arr1[] = {
1,
2,
5,
7,
2,
5,
7,
9,
10,
14
};
//Get the length of array
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.is_sorted_pair(arr1, size);
//Define array elements
int arr2[] = {
6,
7,
4,
6,
9,
5,
2,
1
};
//Get the length of array
size = sizeof(arr2) / sizeof(arr2[0]);
obj.is_sorted_pair(arr2, size);
return 0;
}
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
/*
Java Program
Check if a given array is pairwise sorted or not
*/
public class MyArray {
//Print array elements
public void print_data(int []arr,int size)
{
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
}
//Check whether given array is form of pairwise sorted or not
public void is_sorted_pair(int []arr,int size)
{
if(size<=1)
{
return;
}
else if(size%2!=0)
{
//When array size is odd
System.out.print("Pair length are Odd\n");
}
else{
boolean status = true;
for (int i = 0; i < size-1; i+=2)
{
if(arr[i] > arr[i+1])
{
//When pair is not sorted
status=false;
break;
}
}
//Show array elements
print_data(arr,size);
if(status==true)
{
System.out.print("\n Yes\n");
}
else
{
System.out.print("\n No\n");
}
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Test Case
//Define array elements
int []arr1 ={1,2,5,7,2,5,7,9,10,14};
//Get the length of array
int size=arr1.length;
obj.is_sorted_pair(arr1,size);
//Define array elements
int []arr2 ={6,7,4,6,9,5,2,1};
//Get the length of array
size=arr2.length;
obj.is_sorted_pair(arr2,size);
}
}
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
/*
C# Program
Check if a given array is pairwise sorted or not
*/
using System;
public class MyArray {
//Print array elements
public void print_data(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
//Check whether given array is form of pairwise sorted or not
public void is_sorted_pair(int[] arr, int size) {
if (size <= 1) {
return;
} else if (size % 2 != 0) {
//When array size is odd
Console.Write("Pair.Length are Odd\n");
} else {
Boolean status = true;
for (int i = 0; i < size - 1; i += 2) {
if (arr[i] > arr[i + 1]) {
//When pair is not sorted
status = false;
break;
}
}
//Show array elements
print_data(arr, size);
if (status == true) {
Console.Write("\n Yes\n");
} else {
Console.Write("\n No\n");
}
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Test Case
//Define array elements
int[] arr1 = {
1,
2,
5,
7,
2,
5,
7,
9,
10,
14
};
//Get the.Length of array
int size = arr1.Length;
obj.is_sorted_pair(arr1, size);
//Define array elements
int[] arr2 = {
6,
7,
4,
6,
9,
5,
2,
1
};
//Get the.Length of array
size = arr2.Length;
obj.is_sorted_pair(arr2, size);
}
}
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
<?php
/*
Php Program
Check if a given array is pairwise sorted or not
*/
class MyArray {
//Print array elements
public function print_data($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
}
//Check whether given array is form of pairwise sorted or not
public function is_sorted_pair($arr, $size) {
if ($size <= 1) {
return;
} else
if ($size % 2 != 0) {
//When array size is odd
echo("Pair length are Odd\n");
} else {
$status = true;
for ($i = 0; $i < $size - 1; $i += 2) {
if ($arr[$i] > $arr[$i + 1]) {
//When pair is not sorted
$status = false;
break;
}
}
//Show array elements
$this->print_data($arr, $size);
if ($status == true) {
echo("\n Yes\n");
} else {
echo("\n No\n");
}
}
}
};
function main() {
$obj = new MyArray();
//Test Case
//Define array elements
$arr1 = array(1, 2, 5, 7, 2, 5, 7, 9, 10, 14);
//Get the length of array
$size = count($arr1);
$obj->is_sorted_pair($arr1, $size);
//Define array elements
$arr2 = array(6, 7, 4, 6, 9, 5, 2, 1);
//Get the length of array
$size = count($arr2);
$obj->is_sorted_pair($arr2, $size);
}
main();
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
/*
Node Js Program
Check if a given array is pairwise sorted or not
*/
class MyArray {
//Print array elements
print_data(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
//Check whether given array is form of pairwise sorted or not
is_sorted_pair(arr, size) {
if (size <= 1) {
return;
} else
if (size % 2 != 0) {
//When array size is odd
process.stdout.write("Pair length are Odd\n");
} else {
var status = true;
for (var i = 0; i < size - 1; i += 2) {
if (arr[i] > arr[i + 1]) {
//When pair is not sorted
status = false;
break;
}
}
//Show array elements
this.print_data(arr, size);
if (status == true) {
process.stdout.write("\n Yes\n");
} else {
process.stdout.write("\n No\n");
}
}
}
}
function main(args) {
var obj = new MyArray();
//Test Case
//Define array elements
var arr1 = [1, 2, 5, 7, 2, 5, 7, 9, 10, 14];
//Get the length of array
var size = arr1.length;
obj.is_sorted_pair(arr1, size);
//Define array elements
var arr2 = [6, 7, 4, 6, 9, 5, 2, 1];
//Get the length of array
size = arr2.length;
obj.is_sorted_pair(arr2, size);
}
main();
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
# Python 3 Program
# Check if a given array is pairwise sorted or not
class MyArray :
# Print array elements
def print_data(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i],end="")
i += 1
# Check whether given array is form of pairwise sorted or not
def is_sorted_pair(self, arr, size) :
if (size <= 1) :
return
elif (size % 2 != 0) :
# When array size is odd
print("Pair length are Odd\n")
else :
status = True
i = 0
while (i < size - 1) :
if (arr[i] > arr[i + 1]) :
# When pair is not sorted
status = False
break
i += 2
# Show array elements
self.print_data(arr, size)
if (status == True) :
print("\n Yes")
else :
print("\n No")
def main() :
obj = MyArray()
# Test Case
# Define array elements
arr1 = [1, 2, 5, 7, 2, 5, 7, 9, 10, 14]
# Get the length of array
size = len(arr1)
obj.is_sorted_pair(arr1, size)
# Define array elements
arr2 = [6, 7, 4, 6, 9, 5, 2, 1]
# Get the length of array
size = len(arr2)
obj.is_sorted_pair(arr2, size)
if __name__ == "__main__":
main()
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
# Ruby Program
# Check if a given array is pairwise sorted or not
class MyArray
# Print array elements
def print_data(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
# Check whether given array is form of pairwise sorted or not
def is_sorted_pair(arr, size)
if (size <= 1)
return
elsif (size % 2 != 0)
# When array size is odd
print("Pair length are Odd\n")
else
status = true
i = 0
while (i < size - 1)
if (arr[i] > arr[i + 1])
# When pair is not sorted
status = false
break
end
i += 2
end
# Show array elements
self.print_data(arr, size)
if (status == true)
print("\n Yes\n")
else
print("\n No\n")
end
end
end
end
def main()
obj = MyArray.new()
# Test Case
# Define array elements
arr1 = [1, 2, 5, 7, 2, 5, 7, 9, 10, 14]
# Get the length of array
size = arr1.length
obj.is_sorted_pair(arr1, size)
# Define array elements
arr2 = [6, 7, 4, 6, 9, 5, 2, 1]
# Get the length of array
size = arr2.length
obj.is_sorted_pair(arr2, size)
end
main()
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
/*
Scala Program
Check if a given array is pairwise sorted or not
*/
class MyArray {
//Print array elements
def print_data(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
//Check whether given array is form of pairwise sorted or not
def is_sorted_pair(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
} else
if (size % 2 != 0) {
//When array size is odd
print("Pair length are Odd\n");
} else {
var status: Boolean = true;
var i: Int = 0;
while (i < size - 1 && status == true) {
if (arr(i) > arr(i + 1)) {
//When pair is not sorted
status = false;
}
i += 2;
}
//Show array elements
this.print_data(arr, size);
if (status == true) {
print("\n Yes\n");
} else {
print("\n No\n");
}
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Test Case
//Define array elements
var arr1: Array[Int] = Array(1, 2, 5, 7, 2, 5, 7, 9, 10, 14);
//Get the length of array
var size: Int = arr1.length;
obj.is_sorted_pair(arr1, size);
//Define array elements
var arr2: Array[Int] = Array(6, 7, 4, 6, 9, 5, 2, 1);
//Get the length of array
size = arr2.length;
obj.is_sorted_pair(arr2, size);
}
}
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
/*
Swift 4 Program
Check if a given array is pairwise sorted or not
*/
class MyArray {
//Print array elements
func print_data(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i],terminator:"");
i += 1;
}
}
//Check whether given array is form of pairwise sorted or not
func is_sorted_pair(_ arr: [Int], _ size: Int) {
if (size <= 1) {
return;
} else
if (size % 2 != 0) {
//When array size is odd
print("Pair length are Odd\n");
} else {
var status: Bool = true;
var i: Int = 0;
while (i < size - 1) {
if (arr[i] > arr[i + 1]) {
//When pair is not sorted
status = false;
break;
}
i += 2;
}
//Show array elements
self.print_data(arr, size);
if (status == true) {
print("\n Yes");
} else {
print("\n No");
}
}
}
}
func main() {
let obj: MyArray = MyArray();
//Test Case
//Define array elements
let arr1: [Int] = [1, 2, 5, 7, 2, 5, 7, 9, 10, 14];
//Get the length of array
var size: Int = arr1.count;
obj.is_sorted_pair(arr1, size);
//Define array elements
let arr2: [Int] = [6, 7, 4, 6, 9, 5, 2, 1];
//Get the length of array
size = arr2.count;
obj.is_sorted_pair(arr2, size);
}
main();
Output
1 2 5 7 2 5 7 9 10 14
Yes
6 7 4 6 9 5 2 1
No
Time Complexity
The time complexity of the algorithm is O(n), where n is the size of the input array. This is because we iterate through the array once, comparing each pair of adjacent elements, and the array size directly determines the number of iterations.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment