Given an array arr of size n, the task is to sort this array using minimum swaps. We are allowed to swap only adjacent elements.
Examples:
Input: arr[] = {1, 4, 3, 5, 2}
Output: 4
Explaination:
After 1st swap: arr[] = {1, 4, 3, 2, 5}
After 2nd swap: arr[] = {1, 4, 2, 3, 5}
After 3rd swap: arr[] = {1, 2, 4, 3, 5}
After 4th swap: arr[] = {1, 2, 3, 4, 5}
Input: arr[] = {5, 2, 5, 1, 3}
Output: 6
Naive Approach:
The above problem is an application of the Bubble Sort technique, which repeatedly swaps the adjacent elements if they are in the wrong order.
Below is the implementation of the above approach.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A function to implement bubble sort
int minSwap(int arr[], int n)
{
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
ans++;
}
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 3, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minSwap(arr, n);
return 0;
}
C
// C program for the above approach
#include <stdio.h>
// Function to swap numbers
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
int minSwap(int arr[], int n)
{
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
ans++;
}
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 3, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", minSwap(arr, n));
return 0;
}
Java
// Java program for the above approach
class Cpp {
// A function to implement bubble sort
static int minSwap(int arr[])
{
int n = arr.length;
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
ans++;
}
}
}
return ans;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 4, 3, 5, 2 };
System.out.println(minSwap(arr));
}
}
Python
# Python program for the above approach
# A function to implement bubble sort
def minSwap(arr):
n = len(arr)
ans = 0
for i in range(n - 1):
# Last i elements are already in place
for j in range(n - i - 1):
if (arr[j] > arr[j + 1]):
arr[j], arr[j + 1] = arr[j + 1], arr[j]
ans += 1
return ans
# Driver code
arr = [1, 4, 3, 5, 2]
print(minSwap(arr))
C#
// C# program for the above approach
using System;
class Cpp {
// A function to implement bubble sort
static int minSwap(int[] arr)
{
int n = arr.Length;
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap temp and arr[i]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
ans++;
}
}
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 4, 3, 5, 2 };
Console.WriteLine(minSwap(arr));
}
}
PHP
<?php
// PHP program for the above approach
// A function to implement bubble sort
function minSwap($arr, $n)
{
$ans = 0;
for ($i = 0; $i < $n - 1; $i++) {
// Last i elements are already in place
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$t = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $t;
$ans++;
}
}
}
return $ans;
}
// Driver code
$arr = array( 1, 4, 3, 5, 2 );
$n = sizeof($arr);
echo minSwap($arr, $n);
?>
Output:
4
Time complexity: O(n2)
Auxiliary space: O(1)
Optimized Approach:
The above function always runs O(n2) time even if the array is sorted. It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A function to implement bubble sort
int minSwap(int arr[], int n)
{
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// To check if swap is made or not
int flag = 0;
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = 1;
swap(arr[j], arr[j + 1]);
ans++;
}
}
// If no two elements were swapped
// by inner loop, then return ans
if (flag == 0)
return ans;
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 3, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minSwap(arr, n);
return 0;
}
C
// C program for the above approach
#include <stdio.h>
// Function to swap numbers
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
int minSwap(int arr[], int n)
{
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// To check if swap is made or not
int flag = 0;
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = 1;
swap(&arr[j], &arr[j + 1]);
ans++;
}
}
// IF no two elements were swapped
// by inner loop, then return ans
if (flag == 0)
return ans;
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 3, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", minSwap(arr, n));
return 0;
}
Java
// Java program for the above approach
class Cpp {
// A function to implement bubble sort
static int minSwap(int arr[])
{
int n = arr.length;
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// To check if swap is made or not
int flag = 0;
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = 1;
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
ans++;
}
}
// IF no two elements were swapped
// by inner loop, then return ans
if (flag == 0)
return ans;
}
return ans;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 4, 3, 5, 2 };
System.out.println(minSwap(arr));
}
}
Python
# Python program for the above approach
# A function to implement bubble sort
def minSwap(arr):
n = len(arr)
ans = 0
for i in range(n - 1):
# To check if swap is made or not
flag = 0
# Last i elements are already in place
for j in range(n - i - 1):
if (arr[j] > arr[j + 1]):
flag = 1
arr[j], arr[j + 1] = arr[j + 1], arr[j]
ans += 1
# IF no two elements were swapped
# by inner loop, then return ans
if flag == 0:
return ans
return ans
# Driver code
arr = [1, 4, 3, 5, 2]
print(minSwap(arr))
C#
// C# program for the above approach
using System;
class Cpp {
// A function to implement bubble sort
static int minSwap(int[] arr)
{
int n = arr.Length;
int i, j, ans = 0;
for (i = 0; i < n - 1; i++) {
// To check if swap is made or not
int flag = 0;
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap temp and arr[i]
flag = 1;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
ans++;
}
}
// If no two elements were swapped
// by inner loop, then return ans
if (flag == 0)
return ans;
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 4, 3, 5, 2 };
Console.WriteLine(minSwap(arr));
}
}
PHP
<?php
// PHP program for the above approach
// A function to implement bubble sort
function minSwap($arr, $n)
{
$ans = 0;
for ($i = 0; $i < $n - 1; $i++) {
// To check if swap is made or not
$flag = 0;
// Last i elements are already in place
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$flag = 1;
$t = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $t;
$ans++;
}
}
// If no two elements were swapped
// by inner loop, then return ans
if ($flag == 0)
return $ans;
}
return $ans;
}
// Driver code
$arr = array( 1, 4, 3, 5, 2 );
$n = sizeof($arr);
echo minSwap($arr, $n);
?>
Output:
4
Time complexity: O(n2)
Auxiliary space: O(1)