Número mínimo de intercambios necesarios para ordenar una array | conjunto 2

Dada una array de N elementos distintos, encuentre el número mínimo de intercambios necesarios para ordenar la array.

Nota : el problema no es ordenar la array por el número mínimo de intercambios. El problema es encontrar los intercambios mínimos en los que se puede ordenar la array.

Ejemplos : 

Input: arr[] = {4, 3, 2, 1}
Output: 2
Explanation: Swap index 0 with 3 and 1 with
2 to get the sorted array {1, 2, 3, 4}.

Input: arr[] = { 3, 5, 2, 4, 6, 8}
Output: 3
Explanation: 
Swap 4 and 5 so array = 3, 4, 2, 5, 6, 8
Swap 2 and 3 so array = 2, 4, 3, 5, 6, 8
Swap 4 and 3 so array = 2, 3, 4, 5, 6, 8
So the array is sorted.

Este problema ya se discutió en el artículo anterior usando graph . En este artículo se discute otro enfoque para resolver este problema que es ligeramente diferente del enfoque del ciclo.

Enfoque: 
La idea es crear un vector de pares en C++ con el primer elemento como valores de array y el segundo elemento como índices de array. El siguiente paso es ordenar el vector de par según el primer elemento del par. Después de eso, recorra el vector y verifique si el índice asignado con el valor es correcto o no, de lo contrario, continúe intercambiando hasta que el elemento se coloque correctamente y siga contando el número de intercambios.

Algoritmo: 

1. Cree un vector de pares y recorra la array y para cada elemento de la array inserte un par de índice de elemento en el vector
2. Atraviesa el vector desde el principio hasta el final (el contador de bucle es i).
3. Para cada elemento del par donde el segundo elemento (índice) no es igual a i. Intercambiar el i-ésimo elemento del vector con el segundo elemento (índice) el ésimo elemento del vector
4. Si el segundo elemento (índice) es igual a i, omita la iteración del bucle.
5. si después del intercambio, el segundo elemento (índice) no es igual a i, entonces disminuya i.
6. Incrementa el contador.

Implementación: 

// C++ program to find the minimum number
// of swaps required to sort an array
// of distinct element
 
#include<bits/stdc++.h>
using namespace std;
 
// Function to find minimum swaps to
// sort an array
int findMinSwap(int arr[] , int n)
{
    // Declare a vector of pair    
    vector<pair<int,int>> vec(n);
     
    for(int i=0;i<n;i++)
    {
        vec[i].first=arr[i];
        vec[i].second=i;
    }
 
    // Sort the vector w.r.t the first
    // element of pair
    sort(vec.begin(),vec.end());
 
    int ans=0,c=0,j;
 
    for(int i=0;i<n;i++)
    {  
        // If the element is already placed
        // correct, then continue
        if(vec[i].second==i)
            continue;
        else
        {
            // swap with its respective index
            swap(vec[i].first,vec[vec[i].second].first);
            swap(vec[i].second,vec[vec[i].second].second);
        }
         
        // swap until the correct
        // index matches
        if(i!=vec[i].second)
            --i;
         
        // each swap makes one element
        // move to its correct index,
        // so increment answer
        ans++;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = {1, 5, 4, 3, 2};
     
    int n = sizeof(arr)/sizeof(arr[0]);
     
    cout<<findMinSwap(arr,n);
     
    return 0;
}

// Java program to find the minimum number 
// of swaps required to sort an array
// of distinct element
import java.util.*;
class GFG
{
     
static class Point implements Comparable<Point>
{
     
    public int x, y;   
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
     
    public int compareTo(Point other)
    {
        return this.x - other.x;
    }
}   
      
// Function to find minimum swaps to 
// sort an array
static int findMinSwap(int[] arr, int n)
{
      
    // Declare a vector of pair  
    List<Point> vec = new ArrayList<Point>();
                                            
    for(int i = 0; i < n; i++)
    {
        vec.add(new Point(arr[i], i));
    }
    
    // Sort the vector w.r.t the first
    // element of pair
    Collections.sort(vec);  
    int ans = 0;
    for(int i = 0; i < n; i++)
    { 
          
        // If the element is already placed
        // correct, then continue
        if (vec.get(i).y == i) 
            continue;
        else
        {
              
            // Swap with its respective index 
            Point temp = vec.get(vec.get(i).y);
            vec.set(vec.get(i).y,vec.get(i));
            vec.set(i, temp);
        } 
          
        // Swap until the correct 
        // index matches
        if (i != vec.get(i).y)
            --i;
            
        // Each swap makes one element
        // move to its correct index, 
        // so increment answer
        ans++;
    }
    return ans;
}
  
// Driver Code
public static void main(String []args)
{
    int[] arr = { 1, 5, 4, 3, 2 };
    int n = arr.length;     
    System.out.println(findMinSwap(arr,n));
}
}
 
// This code is contributed by Pratham76

# Python3 program to find the minimum number
# of swaps required to sort an array
# of distinct element
 
# Function to find minimum swaps to
# sort an array
def findMinSwap(arr, n):
     
    # Declare a vector of pair
    vec = []
 
    for i in range(n):
        vec.append([arr[i], i])
 
    # Sort the vector w.r.t the first
    # element of pair
    vec = sorted(vec)
 
    ans, c, j = -1, 0, 0
 
    for i in range(n):
         
        # If the element is already placed
        # correct, then continue
        if(vec[i][1] == i):
            continue
        else:
            # swap with its respective index
            vec[i][0], vec[vec[i][1]][1] = \
                vec[vec[i][1]][1], vec[i][0]
            vec[i][1], vec[vec[i][1]][1] = \
                vec[vec[i][1]][1], vec[i][1]
 
        # swap until the correct
        # index matches
        if(i != vec[i][1]):
            i -= 1
 
        # each swap makes one element
        # move to its correct index,
        # so increment answer
        ans += 1
 
    return ans
 
# Driver code
arr = [1, 5, 4, 3, 2]
n = len(arr)
print(findMinSwap(arr,n))
 
# This code is contributed by mohit kumar 29

// C# program to find the minimum number 
// of swaps required to sort an array
// of distinct element
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find minimum swaps to 
// sort an array
static int findMinSwap(int[] arr, int n)
{
     
    // Declare a vector of pair  
    List<Tuple<int,
               int>> vec = new List<Tuple<int,
                                          int>>();
                                           
    for(int i = 0; i < n; i++)
    {
        vec.Add(new Tuple<int, int>(arr[i], i));
    }
   
    // Sort the vector w.r.t the first
    // element of pair
    vec.Sort();
   
    int ans = 0;
   
    for(int i = 0; i < n; i++)
    { 
         
        // If the element is already placed
        // correct, then continue
        if (vec[i].Item2 == i) 
            continue;
        else
        {
             
            // Swap with its respective index 
            Tuple<int, int> temp = vec[vec[i].Item2];
            vec[vec[i].Item2] = vec[i];
            vec[i] = temp;
        } 
         
        // Swap until the correct 
        // index matches
        if (i != vec[i].Item2)
            --i;
           
        // Each swap makes one element
        // move to its correct index, 
        // so increment answer
        ans++;
    }
    return ans;
}
 
// Driver Code
static void Main()
{
    int[] arr = { 1, 5, 4, 3, 2 };
    int n = arr.Length;
     
    Console.Write(findMinSwap(arr,n));
}
}
 
// This code is contributed by divyeshrabadiya07

2

Análisis de Complejidad: 

• Complejidad Temporal: O(n Log n). 
  El tiempo requerido para ordenar la array es n log n.
• Espacio Auxiliar: O(n). 
  Se crea una array o vector adicional. Entonces, la complejidad del espacio es O(n)