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