Dada una array arr[] de enteros distintos de 1 a N. La tarea es encontrar el número mínimo de intercambios necesarios para ordenar la array.
Ejemplo:
Input: arr[] = { 7, 1, 3, 2, 4, 5, 6 }
Output: 5
Explanation:
i arr swap (indices)
0 [7, 1, 3, 2, 4, 5, 6] swap (0, 3)
1 [2, 1, 3, 7, 4, 5, 6] swap (0, 1)
2 [1, 2, 3, 7, 4, 5, 6] swap (3, 4)
3 [1, 2, 3, 4, 7, 5, 6] swap (4, 5)
4 [1, 2, 3, 4, 5, 7, 6] swap (5, 6)
5 [1, 2, 3, 4, 5, 6, 7]
Therefore, total number of swaps = 5
Input: arr[] = { 2, 3, 4, 1, 5 }
Output: 3
Acercarse:
- Para cada índice en arr[] .
- Compruebe si el elemento actual está en su posición correcta o no. Dado que la array contiene elementos distintos del 1 al N, podemos simplemente comparar el elemento con su índice en la array para verificar si está en la posición correcta.
- Si el elemento actual no está en su posición correcta, intercambie el elemento con el elemento que ha ocupado su lugar.
- De lo contrario, verifique el siguiente índice.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream>
using namespace std;
// Function to find minimum swaps
int minimumSwaps(int arr[],int n)
{
// Initialise count variable
int count = 0;
int i = 0;
while (i < n)
{
// If current element is
// not at the right position
if (arr[i] != i + 1)
{
while (arr[i] != i + 1)
{
int temp = 0;
// Swap current element
// with correct position
// of that element
temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
count++;
}
}
// Increment for next index
// when current element is at
// correct position
i++;
}
return count;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 1, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
// Function to find minimum swaps
cout << minimumSwaps(arr,n) ;
}
// This code is contributed by AnkitRai01
Java
// Java program to find the minimum
// number of swaps required to sort
// the given array
import java.io.*;
import java.util.*;
class GfG {
// Function to find minimum swaps
static int minimumSwaps(int[] arr)
{
// Initialise count variable
int count = 0;
int i = 0;
while (i < arr.length) {
// If current element is
// not at the right position
if (arr[i] != i + 1) {
while (arr[i] != i + 1) {
int temp = 0;
// Swap current element
// with correct position
// of that element
temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
count++;
}
}
// Increment for next index
// when current element is at
// correct position
i++;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 1, 5 };
// Function to find minimum swaps
System.out.println(minimumSwaps(arr));
}
}
Python3
# Python3 program to find the minimum # number of swaps required to sort # the given array # Function to find minimum swaps def minimumSwaps(arr): # Initialise count variable count = 0; i = 0; while (i < len(arr)): # If current element is # not at the right position if (arr[i] != i + 1): while (arr[i] != i + 1): temp = 0; # Swap current element # with correct position # of that element temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; count += 1; # Increment for next index # when current element is at # correct position i += 1; return count; # Driver code if __name__ == '__main__': arr = [ 2, 3, 4, 1, 5 ]; # Function to find minimum swaps print(minimumSwaps(arr)); # This code is contributed by 29AjayKumar
C#
// C# program to find the minimum
// number of swaps required to sort
// the given array
using System;
class GfG
{
// Function to find minimum swaps
static int minimumSwaps(int[] arr)
{
// Initialise count variable
int count = 0;
int i = 0;
while (i < arr.Length)
{
// If current element is
// not at the right position
if (arr[i] != i + 1)
{
while (arr[i] != i + 1)
{
int temp = 0;
// Swap current element
// with correct position
// of that element
temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
count++;
}
}
// Increment for next index
// when current element is at
// correct position
i++;
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 3, 4, 1, 5 };
// Function to find minimum swaps
Console.WriteLine(minimumSwaps(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to find the minimum
// number of swaps required to sort
// the given array
// Function to find minimum swaps
function minimumSwaps(arr)
{
// Initialise count variable
let count = 0;
let i = 0;
while (i < arr.length)
{
// If current element is
// not at the right position
if (arr[i] != i + 1)
{
while (arr[i] != i + 1)
{
let temp = 0;
// Swap current element
// with correct position
// of that element
temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
count++;
}
}
// Increment for next index
// when current element is at
// correct position
i++;
}
return count;
}
// Driver code
let arr = [2, 3, 4, 1, 5 ];
// Function to find minimum swaps
document.write(minimumSwaps(arr));
</script>
Producción:
3
Complejidad de tiempo : O (N) donde N es el tamaño de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por riteshroshan7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA