permutas mínimo requerido para ordenar un arreglo en Java

Aquí, vamos a aprender a obtener / encontrar las permutas mínimos que se requieren para ordenar un arreglo mediante el programa java .

Problema:

En este problema, tendríamos una matriz no ordenada con números naturales distintos consecutivos [1,2,3, .. n] , donde n es el tamaño de la matriz . Tenemos que encontrar el número mínimo de permutas necesarias para ordenar la matriz en orden ascendente .

Nota: Piense y probar por su cuenta antes de mirar a la solución …

Solución:

Este problema puede resolverse fácilmente mediante la observación de la posición real de elementos y su posición actual, el actual posición del elemento en matriz ordenada será el un [cur] -1 ( elemento-1 ), mediante el seguimiento de la posición real del elemento si volvemos al elemento actual entonces no existe un ciclo, entonces contar el tamaño de ese ciclo, el número de permutas será el ciclismo tamaño-1 , hacer esto class todos los ciclos y sumarlos.

Ejemplo:

Deje una matriz: A = [2, 4, 5, 1, 3]

Minimum swaps required to sort an array in Java - 4

Existen dos ciclos:
Ciclo 1: 2 y rarr; 4 y rarr; 1 y rarr; 2
Ciclo 2: 5 y rarr; 3 y rarr; 5

Tamaño de ciclo = número de nodos:
Tamaño del ciclo 1 = 3
Tamaño del ciclo 2 = 2

Número de permutas: (3-1) + (2-1) = 3

Programa:

import java.io.*;
import java.math.*;
import java.util.*;
public class Swap {
static int minimumSwaps(int[] arr) {
int swap=0;
boolean visited[]=new boolean[arr.length];
for(int i=0;i<arr.length;i++){
int j=i,cycle=0;
while(!visited[j]){
visited[j]=true;
j=arr[j]-1;
cycle++;
}
if(cycle!=0)
swap+=cycle-1;
}
return swap;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
int res = minimumSwaps(arr);
System.out.println(res);
scanner.close();
}
}

salida

    4
4 3 2 1
2


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *