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:

1. 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"

2. 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

1. The is_pairwise_sorted function takes an array arr and its size size as input.
2. 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.
3. If the size is odd, it prints a message about odd pair lengths.
4. Otherwise, it initializes the status variable to 1, assuming the array is pairwise sorted.
5. It iterates through the array with a step of 2, comparing adjacent pairs.
6. 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.
7. After the loop, it prints the array elements using the print_data function.
8. Depending on the status, it prints either "Yes" or "No".
9. The print_data function simply prints each element of the array.

Code Solution

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//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;
  
}

  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;
}

 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);
  }
}

 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);
	}
}

  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();

 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();

 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()

 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()

 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);
	}
}

 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();

  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.