Skip to main content

Check if array can be sorted with single swap

Here given code implementation process.

// C program for 
// Check if array can be sorted with single swap
#include <stdio.h>

// Check that given array is sorted or not
int isSorted(int arr[], int n)
{
	for (int i = 1; i < n; ++i)
	{
		if (arr[i - 1] > arr[i])
		{
			return 0;
		}
	}
	return 1;
}
// Swap the array element of given i and j location
void swapElement(int arr[], int i, int j)
{
	// Swap array element
	arr[i] = arr[i] + arr[j];
	arr[j] = arr[i] - arr[j];
	arr[i] = arr[i] - arr[j];
}
// Print array elements
void printArray(int arr[], int n)
{
	printf("\n Array : ");
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
void isSortBySingleSwap(int arr[], int n)
{
	// Define some auxiliary variables
	int count = 0;
	int first = 0;
	int second = 0;
	int result = 0;
	// Count the number of unsorted element
	// And Get first and second unsorted element position
	for (int i = 1; i < n && count <= 2; ++i)
	{
		if (arr[i - 1] > arr[i])
		{
			if (first == 0)
			{
				// Get first unsorted position
				first = i;
			}
			else
			{
				// Get second unsorted element location
				second = i;
			}
			// Increase the unsorted element counter
			count++;
		}
	}
	if (count == 0)
	{
		// When given array is already sorted
		result = 1;
	}
	else if (count <= 2)
	{
		if (count == 1)
		{
			// Swap two adjacent array elements
			swapElement(arr, first, first - 1);
			// Check that after swap array elements is sorted or not
			result = isSorted(arr, n);
			// Back to actual array
			swapElement(arr, first, first - 1);
		}
		else
		{
			// Swap two array elements
			swapElement(arr, second, first - 1);
			// Check that after swap array elements is sorted or not
			result = isSorted(arr, n);
			// Back to actual array
			swapElement(arr, second, first - 1);
		}
	}
	printArray(arr, n);
	if (result == 1)
	{
		printf(" Yes \n");
	}
	else
	{
		printf(" No \n");
	}
}
int main()
{
	// Define array of integer elements
	int arr1[] = {
		9 , 1 , 2 , 3
	};
	int arr2[] = {
		5 , 1 , 7 , 8 , 9
	};
	int arr3[] = {
		1 , 3 , 9 , 5 , 6 , 7 , 4
	};
	int arr4[] = {
		1 , 5 , 2 , 3
	};
	int arr5[] = {
		1 , 6 , 3 , 4 , 5 , 2 , 9
	};
	// Get the size of arr1
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// Test case A
	isSortBySingleSwap(arr1, n);
	// Get the size of arr2
	n = sizeof(arr2) / sizeof(arr2[0]);
	// Test case B
	isSortBySingleSwap(arr2, n);
	// Get the size of arr3
	n = sizeof(arr3) / sizeof(arr3[0]);
	// Test case C
	isSortBySingleSwap(arr3, n);
	// Get the size of arr4
	n = sizeof(arr4) / sizeof(arr4[0]);
	// Test case D
	isSortBySingleSwap(arr4, n);
	// Get the size of arr5
	n = sizeof(arr5) / sizeof(arr5[0]);
	// Test case E
	isSortBySingleSwap(arr5, n);
	return 0;
}

input

 Array :   9  1  2  3
 No

 Array :   5  1  7  8  9
 Yes

 Array :   1  3  9  5  6  7  4
 Yes

 Array :   1  5  2  3
 No

 Array :   1  6  3  4  5  2  9
 Yes
// Java program for
// Check if array can be sorted with single swap
public class OneSwapSort
{
	// Check that given array is sorted or not
	public boolean isSorted(int[] arr, int n)
	{
		for (int i = 1; i < n; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				return false;
			}
		}
		return true;
	}
	// Swap the array element of given i and j location
	public void swapElement(int[] arr, int i, int j)
	{
		// Swap array element
		arr[i] = arr[i] + arr[j];
		arr[j] = arr[i] - arr[j];
		arr[i] = arr[i] - arr[j];
	}
	// Print array elements
	public void printArray(int[] arr, int n)
	{
		System.out.print("\n Array : ");
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	public void isSortBySingleSwap(int[] arr, int n)
	{
		// Define some auxiliary variables
		int count = 0;
		int first = 0;
		int second = 0;
		boolean result = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		for (int i = 1; i < n && count <= 2; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				if (first == 0)
				{
					// Get first unsorted position
					first = i;
				}
				else
				{
					// Get second unsorted element location
					second = i;
				}
				// Increase the unsorted element counter
				count++;
			}
		}
		if (count == 0)
		{
			// When given array is already sorted
			result = true;
		}
		else if (count <= 2)
		{
			if (count == 1)
			{
				// Swap two adjacent array elements
				swapElement(arr, first, first - 1);
				// Check that after swap array elements is sorted or not
				result = isSorted(arr, n);
				// Back to actual array
				swapElement(arr, first, first - 1);
			}
			else
			{
				// Swap two array elements
				swapElement(arr, second, first - 1);
				// Check that after swap array elements is sorted or not
				result = isSorted(arr, n);
				// Back to actual array
				swapElement(arr, second, first - 1);
			}
		}
		printArray(arr, n);
		if (result == true)
		{
			System.out.println(" Yes ");
		}
		else
		{
			System.out.println(" No ");
		}
	}
	public static void main(String[] args)
	{
		OneSwapSort task = new OneSwapSort();
		// Define array of integer elements
		int[] arr1 = {
			9 , 1 , 2 , 3
		};
		int[] arr2 = {
			5 , 1 , 7 , 8 , 9
		};
		int[] arr3 = {
			1 , 3 , 9 , 5 , 6 , 7 , 4
		};
		int[] arr4 = {
			1 , 5 , 2 , 3
		};
		int[] arr5 = {
			1 , 6 , 3 , 4 , 5 , 2 , 9
		};
		// Get the size of arr1
		int n = arr1.length;
		// Test case A
		task.isSortBySingleSwap(arr1, n);
		// Get the size of arr2
		n = arr2.length;
		// Test case B
		task.isSortBySingleSwap(arr2, n);
		// Get the size of arr3
		n = arr3.length;
		// Test case C
		task.isSortBySingleSwap(arr3, n);
		// Get the size of arr4
		n = arr4.length;
		// Test case D
		task.isSortBySingleSwap(arr4, n);
		// Get the size of arr5
		n = arr5.length;
		// Test case E
		task.isSortBySingleSwap(arr5, n);
	}
}

input

 Array :  9 1 2 3
 No

 Array :  5 1 7 8 9
 Yes

 Array :  1 3 9 5 6 7 4
 Yes

 Array :  1 5 2 3
 No

 Array :  1 6 3 4 5 2 9
 Yes
// Include header file
#include <iostream>
using namespace std;

// C++ program for
// Check if array can be sorted with single swap

class OneSwapSort
{
	public:
		// Check that given array is sorted or not
		bool isSorted(int arr[], int n)
		{
			for (int i = 1; i < n; ++i)
			{
				if (arr[i - 1] > arr[i])
				{
					return false;
				}
			}
			return true;
		}
	// Swap the array element of given i and j location
	void swapElement(int arr[], int i, int j)
	{
		// Swap array element
		arr[i] = arr[i] + arr[j];
		arr[j] = arr[i] - arr[j];
		arr[i] = arr[i] - arr[j];
	}
	// Print array elements
	void printArray(int arr[], int n)
	{
		cout << "\n Array : ";
		for (int i = 0; i < n; ++i)
		{
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	void isSortBySingleSwap(int arr[], int n)
	{
		// Define some auxiliary variables
		int count = 0;
		int first = 0;
		int second = 0;
		bool result = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		for (int i = 1; i < n && count <= 2; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				if (first == 0)
				{
					// Get first unsorted position
					first = i;
				}
				else
				{
					// Get second unsorted element location
					second = i;
				}
				// Increase the unsorted element counter
				count++;
			}
		}
		if (count == 0)
		{
			// When given array is already sorted
			result = true;
		}
		else
		{
			if (count <= 2)
			{
				if (count == 1)
				{
					// Swap two adjacent array elements
					this->swapElement(arr, first, first - 1);
					// Check that after swap array elements is sorted or not
					result = this->isSorted(arr, n);
					// Back to actual array
					this->swapElement(arr, first, first - 1);
				}
				else
				{
					// Swap two array elements
					this->swapElement(arr, second, first - 1);
					// Check that after swap array elements is sorted or not
					result = this->isSorted(arr, n);
					// Back to actual array
					this->swapElement(arr, second, first - 1);
				}
			}
		}
		this->printArray(arr, n);
		if (result == true)
		{
			cout << " Yes " << endl;
		}
		else
		{
			cout << " No " << endl;
		}
	}
};
int main()
{
	OneSwapSort *task = new OneSwapSort();
	// Define array of integer elements
	int arr1[] = {
		9 , 1 , 2 , 3
	};
	int arr2[] = {
		5 , 1 , 7 , 8 , 9
	};
	int arr3[] = {
		1 , 3 , 9 , 5 , 6 , 7 , 4
	};
	int arr4[] = {
		1 , 5 , 2 , 3
	};
	int arr5[] = {
		1 , 6 , 3 , 4 , 5 , 2 , 9
	};
	// Get the size of arr1
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// Test case A
	task->isSortBySingleSwap(arr1, n);
	// Get the size of arr2
	n = sizeof(arr2) / sizeof(arr2[0]);
	// Test case B
	task->isSortBySingleSwap(arr2, n);
	// Get the size of arr3
	n = sizeof(arr3) / sizeof(arr3[0]);
	// Test case C
	task->isSortBySingleSwap(arr3, n);
	// Get the size of arr4
	n = sizeof(arr4) / sizeof(arr4[0]);
	// Test case D
	task->isSortBySingleSwap(arr4, n);
	// Get the size of arr5
	n = sizeof(arr5) / sizeof(arr5[0]);
	// Test case E
	task->isSortBySingleSwap(arr5, n);
	return 0;
}

input

 Array :  9 1 2 3
 No

 Array :  5 1 7 8 9
 Yes

 Array :  1 3 9 5 6 7 4
 Yes

 Array :  1 5 2 3
 No

 Array :  1 6 3 4 5 2 9
 Yes
// Include namespace system
using System;
// Csharp program for
// Check if array can be sorted with single swap
public class OneSwapSort
{
	// Check that given array is sorted or not
	public Boolean isSorted(int[] arr, int n)
	{
		for (int i = 1; i < n; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				return false;
			}
		}
		return true;
	}
	// Swap the array element of given i and j location
	public void swapElement(int[] arr, int i, int j)
	{
		// Swap array element
		arr[i] = arr[i] + arr[j];
		arr[j] = arr[i] - arr[j];
		arr[i] = arr[i] - arr[j];
	}
	// Print array elements
	public void printArray(int[] arr, int n)
	{
		Console.Write("\n Array : ");
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void isSortBySingleSwap(int[] arr, int n)
	{
		// Define some auxiliary variables
		int count = 0;
		int first = 0;
		int second = 0;
		Boolean result = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		for (int i = 1; i < n && count <= 2; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				if (first == 0)
				{
					// Get first unsorted position
					first = i;
				}
				else
				{
					// Get second unsorted element location
					second = i;
				}
				// Increase the unsorted element counter
				count++;
			}
		}
		if (count == 0)
		{
			// When given array is already sorted
			result = true;
		}
		else
		{
			if (count <= 2)
			{
				if (count == 1)
				{
					// Swap two adjacent array elements
					this.swapElement(arr, first, first - 1);
					// Check that after swap array elements is sorted or not
					result = this.isSorted(arr, n);
					// Back to actual array
					this.swapElement(arr, first, first - 1);
				}
				else
				{
					// Swap two array elements
					this.swapElement(arr, second, first - 1);
					// Check that after swap array elements is sorted or not
					result = this.isSorted(arr, n);
					// Back to actual array
					this.swapElement(arr, second, first - 1);
				}
			}
		}
		this.printArray(arr, n);
		if (result == true)
		{
			Console.WriteLine(" Yes ");
		}
		else
		{
			Console.WriteLine(" No ");
		}
	}
	public static void Main(String[] args)
	{
		OneSwapSort task = new OneSwapSort();
		// Define array of integer elements
		int[] arr1 = {
			9 , 1 , 2 , 3
		};
		int[] arr2 = {
			5 , 1 , 7 , 8 , 9
		};
		int[] arr3 = {
			1 , 3 , 9 , 5 , 6 , 7 , 4
		};
		int[] arr4 = {
			1 , 5 , 2 , 3
		};
		int[] arr5 = {
			1 , 6 , 3 , 4 , 5 , 2 , 9
		};
		// Get the size of arr1
		int n = arr1.Length;
		// Test case A
		task.isSortBySingleSwap(arr1, n);
		// Get the size of arr2
		n = arr2.Length;
		// Test case B
		task.isSortBySingleSwap(arr2, n);
		// Get the size of arr3
		n = arr3.Length;
		// Test case C
		task.isSortBySingleSwap(arr3, n);
		// Get the size of arr4
		n = arr4.Length;
		// Test case D
		task.isSortBySingleSwap(arr4, n);
		// Get the size of arr5
		n = arr5.Length;
		// Test case E
		task.isSortBySingleSwap(arr5, n);
	}
}

input

 Array :  9 1 2 3
 No

 Array :  5 1 7 8 9
 Yes

 Array :  1 3 9 5 6 7 4
 Yes

 Array :  1 5 2 3
 No

 Array :  1 6 3 4 5 2 9
 Yes
<?php
// Php program for
// Check if array can be sorted with single swap
class OneSwapSort
{
	// Check that given array is sorted or not
	public	function isSorted($arr, $n)
	{
		for ($i = 1; $i < $n; ++$i)
		{
			if ($arr[$i - 1] > $arr[$i])
			{
				return false;
			}
		}
		return true;
	}
	// Swap the array element of given i and j location
	public function swapElement(&$arr, $i, $j)
	{
		// Swap array element
		$arr[$i] = $arr[$i] + $arr[$j];
		$arr[$j] = $arr[$i] - $arr[$j];
		$arr[$i] = $arr[$i] - $arr[$j];
	}
	// Print array elements
	public function printArray($arr, $n)
	{
		echo("\n Array : ");
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
		echo("\n");
	}
	public function isSortBySingleSwap($arr, $n)
	{
		// Define some auxiliary variables
		$count = 0;
		$first = 0;
		$second = 0;
		$result = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		for ($i = 1; $i < $n && $count <= 2; ++$i)
		{
			if ($arr[$i - 1] > $arr[$i])
			{
				if ($first == 0)
				{
					// Get first unsorted position
					$first = $i;
				}
				else
				{
					// Get second unsorted element location
					$second = $i;
				}
				// Increase the unsorted element counter
				$count++;
			}
		}
		if ($count == 0)
		{
			// When given array is already sorted
			$result = true;
		}
		else
		{
			if ($count <= 2)
			{
				if ($count == 1)
				{
					// Swap two adjacent array elements
					$this->swapElement($arr, $first, $first - 1);
					// Check that after swap array elements is sorted or not
					$result = $this->isSorted($arr, $n);
					// Back to actual array
					$this->swapElement($arr, $first, $first - 1);
				}
				else
				{
					// Swap two array elements
					$this->swapElement($arr, $second, $first - 1);
					// Check that after swap array elements is sorted or not
					$result = $this->isSorted($arr, $n);
					// Back to actual array
					$this->swapElement($arr, $second, $first - 1);
				}
			}
		}
		$this->printArray($arr, $n);
		if ($result == true)
		{
			echo(" Yes \n");
		}
		else
		{
			echo(" No \n");
		}
	}
}

function main()
{
	$task = new OneSwapSort();
	// Define array of integer elements
	$arr1 = array(9, 1, 2, 3);
	$arr2 = array(5, 1, 7, 8, 9);
	$arr3 = array(1, 3, 9, 5, 6, 7, 4);
	$arr4 = array(1, 5, 2, 3);
	$arr5 = array(1, 6, 3, 4, 5, 2, 9);
	// Get the size of arr1
	$n = count($arr1);
	// Test case A
	$task->isSortBySingleSwap($arr1, $n);
	// Get the size of arr2
	$n = count($arr2);
	// Test case B
	$task->isSortBySingleSwap($arr2, $n);
	// Get the size of arr3
	$n = count($arr3);
	// Test case C
	$task->isSortBySingleSwap($arr3, $n);
	// Get the size of arr4
	$n = count($arr4);
	// Test case D
	$task->isSortBySingleSwap($arr4, $n);
	// Get the size of arr5
	$n = count($arr5);
	// Test case E
	$task->isSortBySingleSwap($arr5, $n);
}
main();

input

 Array :  9 1 2 3
 No

 Array :  5 1 7 8 9
 Yes

 Array :  1 3 9 5 6 7 4
 Yes

 Array :  1 5 2 3
 No

 Array :  1 6 3 4 5 2 9
 Yes
// Node JS program for
// Check if array can be sorted with single swap
class OneSwapSort
{
	// Check that given array is sorted or not
	isSorted(arr, n)
	{
		for (var i = 1; i < n; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				return false;
			}
		}
		return true;
	}
	// Swap the array element of given i and j location
	swapElement(arr, i, j)
	{
		// Swap array element
		arr[i] = arr[i] + arr[j];
		arr[j] = arr[i] - arr[j];
		arr[i] = arr[i] - arr[j];
	}
	// Print array elements
	printArray(arr, n)
	{
		process.stdout.write("\n Array : ");
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	isSortBySingleSwap(arr, n)
	{
		// Define some auxiliary variables
		var count = 0;
		var first = 0;
		var second = 0;
		var result = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		for (var i = 1; i < n && count <= 2; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				if (first == 0)
				{
					// Get first unsorted position
					first = i;
				}
				else
				{
					// Get second unsorted element location
					second = i;
				}
				// Increase the unsorted element counter
				count++;
			}
		}
		if (count == 0)
		{
			// When given array is already sorted
			result = true;
		}
		else
		{
			if (count <= 2)
			{
				if (count == 1)
				{
					// Swap two adjacent array elements
					this.swapElement(arr, first, first - 1);
					// Check that after swap array elements is sorted or not
					result = this.isSorted(arr, n);
					// Back to actual array
					this.swapElement(arr, first, first - 1);
				}
				else
				{
					// Swap two array elements
					this.swapElement(arr, second, first - 1);
					// Check that after swap array elements is sorted or not
					result = this.isSorted(arr, n);
					// Back to actual array
					this.swapElement(arr, second, first - 1);
				}
			}
		}
		this.printArray(arr, n);
		if (result == true)
		{
			console.log(" Yes ");
		}
		else
		{
			console.log(" No ");
		}
	}
}

function main()
{
	var task = new OneSwapSort();
	// Define array of integer elements
	var arr1 = [9, 1, 2, 3];
	var arr2 = [5, 1, 7, 8, 9];
	var arr3 = [1, 3, 9, 5, 6, 7, 4];
	var arr4 = [1, 5, 2, 3];
	var arr5 = [1, 6, 3, 4, 5, 2, 9];
	// Get the size of arr1
	var n = arr1.length;
	// Test case A
	task.isSortBySingleSwap(arr1, n);
	// Get the size of arr2
	n = arr2.length;
	// Test case B
	task.isSortBySingleSwap(arr2, n);
	// Get the size of arr3
	n = arr3.length;
	// Test case C
	task.isSortBySingleSwap(arr3, n);
	// Get the size of arr4
	n = arr4.length;
	// Test case D
	task.isSortBySingleSwap(arr4, n);
	// Get the size of arr5
	n = arr5.length;
	// Test case E
	task.isSortBySingleSwap(arr5, n);
}
main();

input

 Array :  9 1 2 3
 No

 Array :  5 1 7 8 9
 Yes

 Array :  1 3 9 5 6 7 4
 Yes

 Array :  1 5 2 3
 No

 Array :  1 6 3 4 5 2 9
 Yes
#  Python 3 program for
#  Check if array can be sorted with single swap
class OneSwapSort :
	#  Check that given list is sorted or not
	def isSorted(self, arr, n) :
		i = 1
		while (i < n) :
			if (arr[i - 1] > arr[i]) :
				return False
			
			i += 1
		
		return True
	
	#  Swap the list element of given i and j location
	def swapElement(self, arr, i, j) :
		#  Swap list element
		arr[i] = arr[i] + arr[j]
		arr[j] = arr[i] - arr[j]
		arr[i] = arr[i] - arr[j]
	
	#  Print list elements
	def printArray(self, arr, n) :
		print("\n Array : ", end = "")
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	def isSortBySingleSwap(self, arr, n) :
		count = 0
		first = 0
		second = 0
		result = False
		#  Count the number of unsorted element
		#  And Get first and second unsorted element position
		i = 1
		while (i < n and count <= 2) :
			if (arr[i - 1] > arr[i]) :
				if (first == 0) :
					#  Get first unsorted position
					first = i
				else :
					#  Get second unsorted element location
					second = i
				
				#  Increase the unsorted element counter
				count += 1
			
			i += 1
		
		if (count == 0) :
			#  When given list is already sorted
			result = True
		else :
			if (count <= 2) :
				if (count == 1) :
					#  Swap two adjacent list elements
					self.swapElement(arr, first, first - 1)
					#  Check that after swap list elements is sorted or not
					result = self.isSorted(arr, n)
					#  Back to actual list
					self.swapElement(arr, first, first - 1)
				else :
					#  Swap two list elements
					self.swapElement(arr, second, first - 1)
					#  Check that after swap list elements is sorted or not
					result = self.isSorted(arr, n)
					#  Back to actual list
					self.swapElement(arr, second, first - 1)
				
			
		
		self.printArray(arr, n)
		if (result == True) :
			print(" Yes ")
		else :
			print(" No ")
		
	

def main() :
	task = OneSwapSort()
	arr1 = [9, 1, 2, 3]
	arr2 = [5, 1, 7, 8, 9]
	arr3 = [1, 3, 9, 5, 6, 7, 4]
	arr4 = [1, 5, 2, 3]
	arr5 = [1, 6, 3, 4, 5, 2, 9]
	n = len(arr1)
	#  Test case A
	task.isSortBySingleSwap(arr1, n)
	#  Get the size of arr2
	n = len(arr2)
	#  Test case B
	task.isSortBySingleSwap(arr2, n)
	#  Get the size of arr3
	n = len(arr3)
	#  Test case C
	task.isSortBySingleSwap(arr3, n)
	#  Get the size of arr4
	n = len(arr4)
	#  Test case D
	task.isSortBySingleSwap(arr4, n)
	#  Get the size of arr5
	n = len(arr5)
	#  Test case E
	task.isSortBySingleSwap(arr5, n)

if __name__ == "__main__": main()

input

 Array :   9  1  2  3
 No

 Array :   5  1  7  8  9
 Yes

 Array :   1  3  9  5  6  7  4
 Yes

 Array :   1  5  2  3
 No

 Array :   1  6  3  4  5  2  9
 Yes
#  Ruby program for
#  Check if array can be sorted with single swap
class OneSwapSort 
	#  Check that given array is sorted or not
	def isSorted(arr, n) 
		i = 1
		while (i < n) 
			if (arr[i - 1] > arr[i]) 
				return false
			end

			i += 1
		end

		return true
	end

	#  Swap the array element of given i and j location
	def swapElement(arr, i, j) 
		#  Swap array element
		arr[i] = arr[i] + arr[j]
		arr[j] = arr[i] - arr[j]
		arr[i] = arr[i] - arr[j]
	end

	#  Print array elements
	def printArray(arr, n) 
		print("\n Array : ")
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	def isSortBySingleSwap(arr, n) 
		#  Define some auxiliary variables
		count = 0
		first = 0
		second = 0
		result = false
		#  Count the number of unsorted element
		#  And Get first and second unsorted element position
		i = 1
		while (i < n && count <= 2) 
			if (arr[i - 1] > arr[i]) 
				if (first == 0) 
					#  Get first unsorted position
					first = i
				else 
					#  Get second unsorted element location
					second = i
				end

				#  Increase the unsorted element counter
				count += 1
			end

			i += 1
		end

		if (count == 0) 
			#  When given array is already sorted
			result = true
		else 
			if (count <= 2) 
				if (count == 1) 
					#  Swap two adjacent array elements
					self.swapElement(arr, first, first - 1)
					#  Check that after swap array elements is sorted or not
					result = self.isSorted(arr, n)
					#  Back to actual array
					self.swapElement(arr, first, first - 1)
				else 
					#  Swap two array elements
					self.swapElement(arr, second, first - 1)
					#  Check that after swap array elements is sorted or not
					result = self.isSorted(arr, n)
					#  Back to actual array
					self.swapElement(arr, second, first - 1)
				end

			end

		end

		self.printArray(arr, n)
		if (result == true) 
			print(" Yes ", "\n")
		else 
			print(" No ", "\n")
		end

	end

end

def main() 
	task = OneSwapSort.new()
	#  Define array of integer elements
	arr1 = [9, 1, 2, 3]
	arr2 = [5, 1, 7, 8, 9]
	arr3 = [1, 3, 9, 5, 6, 7, 4]
	arr4 = [1, 5, 2, 3]
	arr5 = [1, 6, 3, 4, 5, 2, 9]
	#  Get the size of arr1
	n = arr1.length
	#  Test case A
	task.isSortBySingleSwap(arr1, n)
	#  Get the size of arr2
	n = arr2.length
	#  Test case B
	task.isSortBySingleSwap(arr2, n)
	#  Get the size of arr3
	n = arr3.length
	#  Test case C
	task.isSortBySingleSwap(arr3, n)
	#  Get the size of arr4
	n = arr4.length
	#  Test case D
	task.isSortBySingleSwap(arr4, n)
	#  Get the size of arr5
	n = arr5.length
	#  Test case E
	task.isSortBySingleSwap(arr5, n)
end

main()

input

 Array :  9 1 2 3
 No 

 Array :  5 1 7 8 9
 Yes 

 Array :  1 3 9 5 6 7 4
 Yes 

 Array :  1 5 2 3
 No 

 Array :  1 6 3 4 5 2 9
 Yes 

// Scala program for
// Check if array can be sorted with single swap
class OneSwapSort()
{
	// Check that given array is sorted or not
	def isSorted(arr: Array[Int], n: Int): Boolean = {
		var i: Int = 1;
		while (i < n)
		{
			if (arr(i - 1) > arr(i))
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// Swap the array element of given i and j location
	def swapElement(arr: Array[Int], i: Int, j: Int): Unit = {
		// Swap array element
		arr(i) = arr(i) + arr(j);
		arr(j) = arr(i) - arr(j);
		arr(i) = arr(i) - arr(j);
	}
	// Print array elements
	def printArray(arr: Array[Int], n: Int): Unit = {
		print("\n Array : ");
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def isSortBySingleSwap(arr: Array[Int], n: Int): Unit = {
		// Define some auxiliary variables
		var count: Int = 0;
		var first: Int = 0;
		var second: Int = 0;
		var result: Boolean = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		var i: Int = 1;
		while (i < n && count <= 2)
		{
			if (arr(i - 1) > arr(i))
			{
				if (first == 0)
				{
					// Get first unsorted position
					first = i;
				}
				else
				{
					// Get second unsorted element location
					second = i;
				}
				// Increase the unsorted element counter
				count += 1;
			}
			i += 1;
		}
		if (count == 0)
		{
			// When given array is already sorted
			result = true;
		}
		else
		{
			if (count <= 2)
			{
				if (count == 1)
				{
					// Swap two adjacent array elements
					swapElement(arr, first, first - 1);
					// Check that after swap array elements is sorted or not
					result = isSorted(arr, n);
					// Back to actual array
					swapElement(arr, first, first - 1);
				}
				else
				{
					// Swap two array elements
					swapElement(arr, second, first - 1);
					// Check that after swap array elements is sorted or not
					result = isSorted(arr, n);
					// Back to actual array
					swapElement(arr, second, first - 1);
				}
			}
		}
		printArray(arr, n);
		if (result == true)
		{
			println(" Yes ");
		}
		else
		{
			println(" No ");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: OneSwapSort = new OneSwapSort();
		// Define array of integer elements
		var arr1: Array[Int] = Array(9, 1, 2, 3);
		var arr2: Array[Int] = Array(5, 1, 7, 8, 9);
		var arr3: Array[Int] = Array(1, 3, 9, 5, 6, 7, 4);
		var arr4: Array[Int] = Array(1, 5, 2, 3);
		var arr5: Array[Int] = Array(1, 6, 3, 4, 5, 2, 9);
		// Get the size of arr1
		var n: Int = arr1.length;
		// Test case A
		task.isSortBySingleSwap(arr1, n);
		// Get the size of arr2
		n = arr2.length;
		// Test case B
		task.isSortBySingleSwap(arr2, n);
		// Get the size of arr3
		n = arr3.length;
		// Test case C
		task.isSortBySingleSwap(arr3, n);
		// Get the size of arr4
		n = arr4.length;
		// Test case D
		task.isSortBySingleSwap(arr4, n);
		// Get the size of arr5
		n = arr5.length;
		// Test case E
		task.isSortBySingleSwap(arr5, n);
	}
}

input

 Array :  9 1 2 3
 No

 Array :  5 1 7 8 9
 Yes

 Array :  1 3 9 5 6 7 4
 Yes

 Array :  1 5 2 3
 No

 Array :  1 6 3 4 5 2 9
 Yes
// Swift 4 program for
// Check if array can be sorted with single swap
class OneSwapSort
{
	// Check that given array is sorted or not
	func isSorted(_ arr: [Int], _ n: Int)->Bool
	{
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i - 1] > arr[i])
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	// Swap the array element of given i and j location
	func swapElement(_ arr: inout[Int], _ i: Int, _ j: Int)
	{
		// Swap array element
		arr[i] = arr[i] + arr[j];
		arr[j] = arr[i] - arr[j];
		arr[i] = arr[i] - arr[j];
	}
	// Print array elements
	func printArray(_ arr: [Int], _ n: Int)
	{
		print("\n Array : ", terminator: "");
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	func isSortBySingleSwap(_ arr: inout[Int], _ n: Int)
	{
		// Define some auxiliary variables
		var count: Int = 0;
		var first: Int = 0;
		var second: Int = 0;
		var result: Bool = false;
		// Count the number of unsorted element
		// And Get first and second unsorted element position
		var i: Int = 1;
		while (i < n && count <= 2)
		{
			if (arr[i - 1] > arr[i])
			{
				if (first == 0)
				{
					// Get first unsorted position
					first = i;
				}
				else
				{
					// Get second unsorted element location
					second = i;
				}
				// Increase the unsorted element counter
				count += 1;
			}
			i += 1;
		}
		if (count == 0)
		{
			// When given array is already sorted
			result = true;
		}
		else
		{
			if (count <= 2)
			{
				if (count == 1)
				{
					// Swap two adjacent array elements
					self.swapElement(&arr, first, first - 1);
					// Check that after swap array elements is sorted or not
					result = self.isSorted(arr, n);
					// Back to actual array
					self.swapElement(&arr, first, first - 1);
				}
				else
				{
					// Swap two array elements
					self.swapElement(&arr, second, first - 1);
					// Check that after swap array elements is sorted or not
					result = self.isSorted(arr, n);
					// Back to actual array
					self.swapElement(&arr, second, first - 1);
				}
			}
		}
		self.printArray(arr, n);
		if (result == true)
		{
			print(" Yes ");
		}
		else
		{
			print(" No ");
		}
	}
}
func main()
{
	let task: OneSwapSort = OneSwapSort();
	// Define array of integer elements
	var arr1: [Int] = [9, 1, 2, 3];
	var arr2: [Int] = [5, 1, 7, 8, 9];
	var arr3: [Int] = [1, 3, 9, 5, 6, 7, 4];
	var arr4: [Int] = [1, 5, 2, 3];
	var arr5: [Int] = [1, 6, 3, 4, 5, 2, 9];
	// Get the size of arr1
	var n: Int = arr1.count;
	// Test case A
	task.isSortBySingleSwap(&arr1, n);
	// Get the size of arr2
	n = arr2.count;
	// Test case B
	task.isSortBySingleSwap(&arr2, n);
	// Get the size of arr3
	n = arr3.count;
	// Test case C
	task.isSortBySingleSwap(&arr3, n);
	// Get the size of arr4
	n = arr4.count;
	// Test case D
	task.isSortBySingleSwap(&arr4, n);
	// Get the size of arr5
	n = arr5.count;
	// Test case E
	task.isSortBySingleSwap(&arr5, n);
}
main();

input

 Array :   9  1  2  3
 No

 Array :   5  1  7  8  9
 Yes

 Array :   1  3  9  5  6  7  4
 Yes

 Array :   1  5  2  3
 No

 Array :   1  6  3  4  5  2  9
 Yes
Last updated on by Kalkicode




Comment

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