Dada una array de n elementos distintos, encuentre el número mínimo de intercambios necesarios para ordenar la array.
Ejemplos:
Input: {4, 3, 2, 1}
Output: 2
Explanation: Swap index 0 with 3 and 1 with 2 to
form the sorted array {1, 2, 3, 4}.
Input: {1, 5, 4, 3, 2}
Output: 2
Esto se puede hacer fácilmente visualizando el problema como un gráfico. Tendremos n Nodes y un borde dirigido desde el Node i al Node j si el elemento en el i-ésimo índice debe estar presente en el j-ésimo índice en la array ordenada.
Graph for {4, 3, 2, 1}
El gráfico ahora contendrá muchos ciclos que no se cruzan. Ahora, un ciclo con 2 Nodes solo requerirá 1 intercambio para alcanzar el orden correcto, de manera similar, un ciclo con 3 Nodes solo requerirá 2 intercambios para hacerlo.
Graph for {4, 5, 2, 1, 3}
Por eso,
- respuesta = Σ i = 1 k (cycle_size – 1)
donde, k es el número de ciclos
A continuación se muestra la implementación de la idea.
C++
// C++ program to find
// minimum number of swaps
// required to sort an array
#include<bits/stdc++.h>
using namespace std;
// Function returns the
// minimum number of swaps
// required to sort the array
int minSwaps(int arr[], int n)
{
// Create an array of
// pairs where first
// element is array element
// and second element
// is position of first element
pair<int, int> arrPos[n];
for (int i = 0; i < n; i++)
{
arrPos[i].first = arr[i];
arrPos[i].second = i;
}
// Sort the array by array
// element values to
// get right position of
// every element as second
// element of pair.
sort(arrPos, arrPos + n);
// To keep track of visited elements.
// Initialize
// all elements as not visited or false.
vector<bool> vis(n, false);
// Initialize result
int ans = 0;
// Traverse array elements
for (int i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrPos[i].second == i)
continue;
// find out the number of node in
// this cycle and add in ans
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = 1;
// move to next node
j = arrPos[j].second;
cycle_size++;
}
// Update answer by adding current cycle.
if (cycle_size > 0)
{
ans += (cycle_size - 1);
}
}
// Return result
return ans;
}
// Driver program to test the above function
int main()
{
int arr[] = {1, 5, 4, 3, 2};
int n = (sizeof(arr) / sizeof(int));
cout << minSwaps(arr, n);
return 0;
}
Java
// Java program to find
// minimum number of swaps
// required to sort an array
import javafx.util.Pair;
import java.util.ArrayList;
import java.util.*;
class GfG
{
// Function returns the
// minimum number of swaps
// required to sort the array
public static int minSwaps(int[] arr)
{
int n = arr.length;
// Create two arrays and
// use as pairs where first
// array is element and second array
// is position of first element
ArrayList <Pair <Integer, Integer> > arrpos =
new ArrayList <Pair <Integer,
Integer> > ();
for (int i = 0; i < n; i++)
arrpos.add(new Pair <Integer,
Integer> (arr[i], i));
// Sort the array by array element values to
// get right position of every element as the
// elements of second array.
arrpos.sort(new Comparator<Pair<Integer,
Integer>>()
{
@Override
public int compare(Pair<Integer, Integer> o1,
Pair<Integer, Integer> o2)
{
if (o1.getKey() > o2.getKey())
return -1;
// We can change this to make
// it then look at the
// words alphabetical order
else if (o1.getKey().equals(o2.getKey()))
return 0;
else
return 1;
}
});
// To keep track of visited elements. Initialize
// all elements as not visited or false.
Boolean[] vis = new Boolean[n];
Arrays.fill(vis, false);
// Initialize result
int ans = 0;
// Traverse array elements
for (int i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrpos.get(i).getValue() == i)
continue;
// find out the number of node in
// this cycle and add in ans
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = true;
// move to next node
j = arrpos.get(j).getValue();
cycle_size++;
}
// Update answer by adding current cycle.
if(cycle_size > 0)
{
ans += (cycle_size - 1);
}
}
// Return result
return ans;
}
}
// Driver class
class MinSwaps
{
// Driver program to test the above function
public static void main(String[] args)
{
int []a = {1, 5, 4, 3, 2};
GfG g = new GfG();
System.out.println(g.minSwaps(a));
}
}
// This code is contributed by Saksham Seth
Python3
# Python3 program to find
# minimum number of swaps
# required to sort an array
# Function returns the minimum
# number of swaps required to
# sort the array
def minSwaps(arr):
n = len(arr)
# Create two arrays and use
# as pairs where first array
# is element and second array
# is position of first element
arrpos = [*enumerate(arr)]
# Sort the array by array element
# values to get right position of
# every element as the elements
# of second array.
arrpos.sort(key = lambda it : it[1])
# To keep track of visited elements.
# Initialize all elements as not
# visited or false.
vis = {k : False for k in range(n)}
# Initialize result
ans = 0
for i in range(n):
# already swapped or
# already present at
# correct position
if vis[i] or arrpos[i][0] == i:
continue
# find number of nodes
# in this cycle and
# add it to ans
cycle_size = 0
j = i
while not vis[j]:
# mark node as visited
vis[j] = True
# move to next node
j = arrpos[j][0]
cycle_size += 1
# update answer by adding
# current cycle
if cycle_size > 0:
ans += (cycle_size - 1)
# return answer
return ans
# Driver Code
arr = [1, 5, 4, 3, 2]
print(minSwaps(arr))
# This code is contributed
# by Dharan Aditya
C#
// C# program to find
// minimum number of swaps
// required to sort an array
using System;
using System.Collections.Generic;
using System.Linq;
public class GfG
{
// Function returns the
// minimum number of swaps
// required to sort the array
public int minSwaps(int[] arr)
{
int n = arr.Length;
// Create two arrays and
// use as pairs where first
// array is element and second array
// is position of first element
List <KeyValuePair <int, int> > arrpos =
new List <KeyValuePair <int, int> > ();
for (int i = 0; i < n; i++)
arrpos.Add(new KeyValuePair <int,
int> (arr[i], i));
// Sort the array by array element values to
// get right position of every element as the
// elements of second array.
arrpos.Sort((a,b)=> a.Key-b.Key);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
Boolean[] vis = new Boolean[n];
// Initialize result
int ans = 0;
// Traverse array elements
for (int i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrpos[i].Value == i)
continue;
// find out the number of node in
// this cycle and add in ans
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = true;
// move to next node
j = arrpos[j].Value;
cycle_size++;
}
// Update answer by adding current cycle.
if(cycle_size > 0)
{
ans += (cycle_size - 1);
}
}
// Return result
return ans;
}
}
// Driver class
public class MinSwaps
{
// Driver program to test the above function
public static void Main(String[] args)
{
int []a = {1, 5, 4, 3, 2};
GfG g = new GfG();
Console.WriteLine(g.minSwaps(a));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find
// minimum number of swaps
// required to sort an array
// Function returns the
// minimum number of swaps
// required to sort the array
function minSwaps(arr)
{
let n = arr.length;
// Create two arrays and
// use as pairs where first
// array is element and second array
// is position of first element
let arrpos = [];
for (let i = 0; i < n; i++)
arrpos.push([arr[i], i]);
// Sort the array by array element values to
// get right position of every element as the
// elements of second array.
arrpos.sort(function(a,b){return a[0]-b[0];});
// To keep track of visited elements. Initialize
// all elements as not visited or false.
let vis = new Array(n);
for(let i=0;i<n;i++)
{
vis[i]=false;
}
// Initialize result
let ans = 0;
// Traverse array elements
for (let i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrpos[i][1] == i)
continue;
// find out the number of node in
// this cycle and add in ans
let cycle_size = 0;
let j = i;
while (!vis[j])
{
vis[j] = true;
// move to next node
j = arrpos[j][1];
cycle_size++;
}
// Update answer by adding current cycle.
if(cycle_size > 0)
{
ans += (cycle_size - 1);
}
}
// Return result
return ans;
}
// Driver class
let a=[1, 5, 4, 3, 2];
document.write(minSwaps(a))
// This code is contributed by ab2127
</script>
Producción
2
Complejidad de Tiempo: O(n Log n)
Espacio Auxiliar: O(n)
Enfoque: como clase de par disponible en Java desde Java 8, podemos usar hashmap en una versión anterior de Java.
A continuación se muestra la implementación de la idea.
C++
#include <bits/stdc++.h>
using namespace std;
// Function returns the
// minimum number of swaps
// required to sort the array
int minSwaps(int nums[], int n)
{
int len = n;
map<int, int> map;
for (int i = 0; i < len; i++)
map[nums[i]] = i;
sort(nums, nums + n);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
bool visited[len] = { 0 };
// Initialize result
int ans = 0;
for (int i = 0; i < len; i++) {
// already swapped and corrected or
// already present at correct pos
if (visited[i] || map[nums[i]] == i)
continue;
int j = i, cycle_size = 0;
while (!visited[j]) {
visited[j] = true;
// move to next node
j = map[nums[j]];
cycle_size++;
}
// Update answer by adding current cycle.
if (cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
int main()
{
// Driver program to test the above function
int a[] = { 1, 5, 4, 3, 2 };
int n = 5;
cout << minSwaps(a, n);
return 0;
}
// This code is contributed by Harshal Khond
Java
import java.util.*;
import java.io.*;
class GfG
{
// Function returns the
// minimum number of swaps
// required to sort the array
public static int minSwaps(int[] nums)
{
int len = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0;i<len;i++)
map.put(nums[i], i);
Arrays.sort(nums);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
boolean[] visited = new boolean[len];
Arrays.fill(visited, false);
// Initialize result
int ans = 0;
for(int i=0;i<len;i++) {
// already swapped and corrected or
// already present at correct pos
if(visited[i] || map.get(nums[i]) == i)
continue;
int j = i, cycle_size = 0;
while(!visited[j]) {
visited[j] = true;
// move to next node
j = map.get(nums[j]);
cycle_size++;
}
// Update answer by adding current cycle.
if(cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
}
// Driver class
class MinSwaps
{
// Driver program to test the above function
public static void main(String[] args)
{
int []a = {1, 5, 4, 3, 2};
GfG g = new GfG();
System.out.println(g.minSwaps(a));
}
}
// This code is contributed by Saurabh Johari
Python3
# Function returns the
# minimum number of swaps
# required to sort the array
from functools import cmp_to_key
def cmp(a, b):
return a - b
def minSwaps(nums):
Len = len(nums)
map = {}
for i in range(Len):
map[nums[i]] = i
nums = sorted(nums, key = cmp_to_key(cmp))
# To keep track of visited elements. Initialize
# all elements as not visited or false.
visited = [False for col in range(Len)]
# Initialize result
ans = 0
for i in range(Len):
# already swapped and corrected or
# already present at correct pos
if (visited[i] or map[nums[i]] == i):
continue
j,cycle_size = i, 0
while (visited[j] == False):
visited[j] = True
# move to next node
j = map[nums[j]]
cycle_size += 1
# Update answer by adding current cycle.
if (cycle_size > 0):
ans += (cycle_size - 1)
return ans
# Driver program to test the above function
a = [ 1, 5, 4, 3, 2 ]
print(minSwaps(a))
# This code is contributed by shinjanpatra
C#
using System;
using System.Collections.Generic;
class GfG
{
// Function returns the
// minimum number of swaps
// required to sort the array
public int minSwaps(int[] nums) {
int len = nums.Length;
Dictionary<int, int> map = new Dictionary<int,int>();
for (int i = 0; i < len; i++)
map.Add(nums[i], i);
Array.Sort(nums);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
bool[] visited = new bool[len];
// Initialize result
int ans = 0;
for (int i = 0; i < len; i++) {
// already swapped and corrected or
// already present at correct pos
if (visited[i] || map[nums[i]] == i)
continue;
int j = i, cycle_size = 0;
while (!visited[j]) {
visited[j] = true;
// move to next node
j = map[nums[j]];
cycle_size++;
}
// Update answer by adding current cycle.
if (cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
}
// Driver class
public class MinSwaps
{
// Driver program to test the above function
public static void Main(String[] args) {
int[] a = { 1, 5, 4, 3, 2 };
GfG g = new GfG();
Console.WriteLine(g.minSwaps(a));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Function returns the
// minimum number of swaps
// required to sort the array
function minSwaps(nums) {
var len = nums.length;
var map = new Map();
for (i = 0; i < len; i++)
map.set(nums[i], i);
nums.sort((a,b)=>a-b);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
var visited = Array(len).fill(false);
// Initialize result
var ans = 0;
for (var i = 0; i < len; i++) {
// already swapped and corrected or
// already present at correct pos
if (visited[i] || map.get(nums[i]) == i)
continue;
var j = i, cycle_size = 0;
while (!visited[j]) {
visited[j] = true;
// move to next node
j = map.get(nums[j]);
cycle_size++;
}
// Update answer by adding current cycle.
if (cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
// Driver program to test the above function
var a = [ 1, 5, 4, 3, 2 ];
document.write(minSwaps(a));
// This code is contributed by Rajput-Ji
</script>
Producción
2
Complejidad de tiempo : O(n Log n)
Espacio auxiliar: O(n)
Solución directa
Mientras itera sobre la array, verifique el elemento actual y, si no está en el lugar correcto, reemplace ese elemento con el índice del elemento que debería haber estado en este lugar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum number
// of swaps required to sort an array
#include <bits/stdc++.h>
using namespace std;
void swap(vector<int> &arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int indexOf(vector<int> &arr, int ele)
{
for(int i = 0; i < arr.size(); i++)
{
if (arr[i] == ele)
{
return i;
}
}
return -1;
}
// Return the minimum number
// of swaps required to sort the array
int minSwaps(vector<int> arr, int N)
{
int ans = 0;
vector<int> temp(arr.begin(),arr.end());
sort(temp.begin(),temp.end());
for(int i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
// Swap the current element
// with the right index
// so that arr[0] to arr[i] is sorted
swap(arr, i, indexOf(arr, temp[i]));
}
}
return ans;
}
// Driver Code
int main()
{
vector<int> a = {101, 758, 315, 730,
472, 619, 460, 479};
int n = a.size();
// Output will be 5
cout << minSwaps(a, n);
}
// This code is contributed by mohit kumar 29
Java
// Java program to find
// minimum number of swaps
// required to sort an array
import java.util.*;
import java.io.*;
class GfG
{
// Return the minimum number
// of swaps required to sort the array
public int minSwaps(int[] arr, int N)
{
int ans = 0;
int[] temp = Arrays.copyOfRange(arr, 0, N);
Arrays.sort(temp);
for (int i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
// Swap the current element
// with the right index
// so that arr[0] to arr[i] is sorted
swap(arr, i, indexOf(arr, temp[i]));
}
}
return ans;
}
public void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public int indexOf(int[] arr, int ele)
{
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == ele) {
return i;
}
}
return -1;
}
}
// Driver class
class Main
{
// Driver program to test
// the above function
public static void main(String[] args)
throws Exception
{
int[] a
= { 101, 758, 315, 730, 472,
619, 460, 479 };
int n = a.length;
// Output will be 5
System.out.println(new GfG().minSwaps(a, n));
}
}
// This code is contributed by Satvik Nema
Python3
# Python3 program to find #minimum number of swaps # required to sort an array # Return the minimum number # of swaps required to sort # the array def minSwaps(arr, N): ans = 0 temp = arr.copy() temp.sort() for i in range(N): # This is checking whether # the current element is # at the right place or not if (arr[i] != temp[i]): ans += 1 # Swap the current element # with the right index # so that arr[0] to arr[i] # is sorted swap(arr, i, indexOf(arr, temp[i])) return ans def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp def indexOf(arr, ele): for i in range(len(arr)): if (arr[i] == ele): return i return -1 # Driver code if __name__ == "__main__": a = [101, 758, 315, 730, 472, 619, 460, 479] n = len(a) # Output will be 5 print(minSwaps(a, n)) # This code is contributed by Chitranayal
C#
// C# program to find
// minimum number of swaps
// required to sort an array
using System;
public class GFG
{
// Return the minimum number
// of swaps required to sort the array
static int minSwaps(int[] arr, int N)
{
int ans = 0;
int[] temp = new int[N];
Array.Copy(arr, temp, N);
Array.Sort(temp);
for (int i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
// Swap the current element
// with the right index
// so that arr[0] to arr[i] is sorted
swap(arr, i, indexOf(arr, temp[i]));
}
}
return ans;
}
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int indexOf(int[] arr, int ele)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == ele) {
return i;
}
}
return -1;
}
// Driver program to test
// the above function
static public void Main (){
int[] a
= { 101, 758, 315, 730, 472,
619, 460, 479 };
int n = a.Length;
// Output will be 5
Console.WriteLine(minSwaps(a, n));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program to find
// minimum number of swaps
// required to sort an array
// Return the minimum number
// of swaps required to sort the array
function minSwaps(arr,N)
{
let ans = 0;
let temp = [...arr];
temp.sort(function(a,b){return a-b;});
for (let i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
// Swap the current element
// with the right index
// so that arr[0] to arr[i] is sorted
swap(arr, i, indexOf(arr, temp[i]));
}
}
return ans;
}
function swap(arr,i,j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function indexOf(arr,ele)
{
for (let i = 0; i < arr.length; i++)
{
if (arr[i] == ele) {
return i;
}
}
return -1;
}
// Driver class
let a=[101, 758, 315, 730, 472,
619, 460, 479 ];
let n = a.length;
document.write(minSwaps(a, n));
// This code is contributed by unknown2108
</script>
Producción
5
Complejidad temporal: O(n*n)
Espacio auxiliar: O(n)
Todavía podemos mejorar la complejidad usando un hashmap. La operación principal aquí es el método indexOf dentro del bucle, que nos cuesta n*n. Podemos mejorar esta sección a O(n), usando un hashmap para almacenar los índices. Aún así, usamos el método de clasificación, por lo que la complejidad no puede mejorar más allá de O (n Log n)
Método usando HashMap:
Igual que antes, cree una nueva array (llamada temp), que es la forma ordenada de la array de entrada. Sabemos que necesitamos transformar la array de entrada en la nueva array (temp) en el número mínimo de intercambios. Haz un mapa que almacene los elementos y su índice correspondiente, de la array de entrada.
Entonces, en cada i comenzando de 0 a N en la array dada, donde N es el tamaño de la array:
- 1. Si i no está en su posición correcta de acuerdo con la array ordenada, entonces
- 2. Llenaremos esta posición con el elemento correcto del hashmap que construimos anteriormente. Sabemos que el elemento correcto que debería aparecer aquí es temp[i], por lo que buscamos el índice de este elemento en el hashmap.
- 3. Después de intercambiar los elementos requeridos, actualizamos el contenido del hashmap en consecuencia, como temp[i] a la i-ésima posición, y arr[i] a donde estaba temp[i] antes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find
// minimum number of swaps
// required to sort an array
#include<bits/stdc++.h>
using namespace std;
void swap(vector<int> &arr,
int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Return the minimum number
// of swaps required to sort
// the array
int minSwaps(vector<int>arr,
int N)
{
int ans = 0;
vector<int>temp = arr;
// Hashmap which stores the
// indexes of the input array
map <int, int> h;
sort(temp.begin(), temp.end());
for (int i = 0; i < N; i++)
{
h[arr[i]] = i;
}
for (int i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
int init = arr[i];
// If not, swap this element
// with the index of the
// element which should come here
swap(arr, i, h[temp[i]]);
// Update the indexes in
// the hashmap accordingly
h[init] = h[temp[i]];
h[temp[i]] = i;
}
}
return ans;
}
// Driver class
int main()
{
// Driver program to
// test the above function
vector <int> a = {101, 758, 315,
730, 472, 619,
460, 479};
int n = a.size();
// Output will be 5
cout << minSwaps(a, n);
}
// This code is contributed by Stream_Cipher
Java
// Java program to find
// minimum number of swaps
// required to sort an array
import java.util.*;
import java.io.*;
class GfG
{
// Return the minimum number
// of swaps required to sort the array
public int minSwaps(int[] arr, int N)
{
int ans = 0;
int[] temp = Arrays.copyOfRange(arr, 0, N);
// Hashmap which stores the
// indexes of the input array
HashMap<Integer, Integer> h
= new HashMap<Integer, Integer>();
Arrays.sort(temp);
for (int i = 0; i < N; i++)
{
h.put(arr[i], i);
}
for (int i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
int init = arr[i];
// If not, swap this element
// with the index of the
// element which should come here
swap(arr, i, h.get(temp[i]));
// Update the indexes in
// the hashmap accordingly
h.put(init, h.get(temp[i]));
h.put(temp[i], i);
}
}
return ans;
}
public void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Driver class
class Main
{
// Driver program to test the above function
public static void main(String[] args)
throws Exception
{
int[] a
= { 101, 758, 315, 730, 472,
619, 460, 479 };
int n = a.length;
// Output will be 5
System.out.println(new GfG().minSwaps(a, n));
}
}
// This code is contributed by Satvik Nema
Python3
# Python3 program to find
# minimum number of swaps
# required to sort an array
# Return the minimum number
# of swaps required to sort
# the array
def minSwap(arr, n):
ans = 0
temp = arr.copy()
# Dictionary which stores the
# indexes of the input array
h = {}
temp.sort()
for i in range(n):
#h.[arr[i]
h[arr[i]] = i
init = 0
for i in range(n):
# This is checking whether
# the current element is
# at the right place or not
if (arr[i] != temp[i]):
ans += 1
init = arr[i]
# If not, swap this element
# with the index of the
# element which should come here
arr[i], arr[h[temp[i]]] = arr[h[temp[i]]], arr[i]
# Update the indexes in
# the hashmap accordingly
h[init] = h[temp[i]]
h[temp[i]] = i
return ans
# Driver code
a = [ 101, 758, 315, 730,
472, 619, 460, 479 ]
n = len(a)
# Output will be 5
print(minSwap(a, n))
# This code is contributed by avanitrachhadiya2155
C#
// C# program to find
// minimum number of swaps
// required to sort an array
using System;
using System.Collections.Generic;
using System.Linq;
public class GfG {
// Return the minimum number
// of swaps required to sort the array
public int minSwaps(int[] arr, int N) {
int ans = 0;
int[] temp = new int[N];
arr.CopyTo(temp,0);
// Hashmap which stores the
// indexes of the input array
Dictionary<int, int> h = new Dictionary<int, int>();
Array.Sort(temp);
for (int i = 0; i < N; i++) {
h.Add(arr[i], i);
}
for (int i = 0; i < N; i++) {
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i]) {
ans++;
int init = arr[i];
// If not, swap this element
// with the index of the
// element which should come here
swap(arr, i, h[temp[i]]);
// Update the indexes in
// the hashmap accordingly
h[init]= h[temp[i]];
h[temp[i]]= i;
}
}
return ans;
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Driver class
public class GFG {
public static void Main(String[] args)
{
int[] a = { 101, 758, 315, 730, 472, 619, 460, 479 };
int n = a.Length;
// Output will be 5
Console.WriteLine(new GfG().minSwaps(a, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find
// minimum number of swaps
// required to sort an array
function swap(arr, i, j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Return the minimum number
// of swaps required to sort
// the array
function minSwaps(arr,N)
{
let ans = 0;
let temp = arr.slice();
// Hashmap which stores the
// indexes of the input array
let h = new Map();
temp.sort();
for (let i = 0; i < N; i++)
{
h.set(arr[i], i);
}
for (let i = 0; i < N; i++)
{
// This is checking whether
// the current element is
// at the right place or not
if (arr[i] != temp[i])
{
ans++;
let init = arr[i];
// If not, swap this element
// with the index of the
// element which should come here
swap(arr, i, h.get(temp[i]));
// Update the indexes in
// the hashmap accordingly
h.set(init,h.get(temp[i]));
h.set(temp[i],i);
}
}
return ans;
}
// Driver class
// Driver program to
// test the above function
let a = [101, 758, 315, 730, 472, 619, 460, 479];
let n = a.length;
// Output will be 5
document.write(minSwaps(a, n));
// This code is contributed by shinjanpatra
</script>
Producción
5
Complejidad de Tiempo: O(n Log n)
Espacio Auxiliar: O(n)
Artículo relacionado:
Número de intercambios para clasificar cuando solo se permiten intercambios adyacentes
Este artículo es una contribución de Ayush Khanduri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA