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)