Dada una array de números enteros, necesitamos ordenar esta array en un número mínimo de pasos donde en un paso podemos insertar cualquier elemento de la array desde su posición a cualquier otra posición.
Ejemplos:
Input : arr[] = [2, 3, 5, 1, 4, 7, 6]
Output : 3
We can sort above array in 3 insertion
steps as shown below,
1 before array value 2
4 before array value 5
6 before array value 7
Input : arr[] = {4, 6, 5, 1}
Output : 2
Podemos resolver este problema usando programación dinámica. Lo principal a observar es que mover un elemento no cambia el orden relativo de los elementos que no sean el elemento que se está moviendo. Ahora considere la subsecuencia creciente más larga (LIS) en la que elementos iguales también se toman como parte de la secuencia creciente, ahora si mantiene el elemento de esta secuencia creciente como está y mueve todos los demás elementos, tomará la menor cantidad de pasos porque han tomado la subsecuencia más larga que no necesita ser movida. Finalmente, la respuesta será el tamaño de la array menos el tamaño de la subsecuencia creciente más larga.
Como el problema LIS se puede resolver en O (N ^ 2) con O (N) espacio adicional usando Programación Dinámica.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to get minimum number of insertion
// steps to sort an array
#include <bits/stdc++.h>
using namespace std;
// method returns min steps of insertion we need
// to perform to sort array 'arr'
int minInsertionStepToSortArray(int arr[], int N)
{
// lis[i] is going to store length of lis
// that ends with i.
int lis[N];
/* Initialize lis values for all indexes */
for (int i = 0; i < N; i++)
lis[i] = 1;
/* Compute optimized lis values in bottom up manner */
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] >= arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* The overall LIS must end with of the array
elements. Pick maximum of all lis values */
int max = 0;
for (int i = 0; i < N; i++)
if (max < lis[i])
max = lis[i];
// return size of array minus length of LIS
// as final result
return (N - max);
}
// Driver code to test above methods
int main()
{
int arr[] = {2, 3, 5, 1, 4, 7, 6};
int N = sizeof(arr) / sizeof(arr[0]);
cout << minInsertionStepToSortArray(arr, N);
return 0;
}
Java
// Java program to get minimum number of insertion
// steps to sort an array
class Main
{
// method returns min steps of insertion we need
// to perform to sort array 'arr'
static int minInsertionStepToSortArray(int arr[], int N)
{
// lis[i] is going to store length of lis
// that ends with i.
int[] lis = new int[N];
/* Initialize lis values for all indexes */
for (int i = 0; i < N; i++)
lis[i] = 1;
/* Compute optimized lis values in bottom up manner */
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] >= arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* The overall LIS must end with of the array
elements. Pick maximum of all lis values */
int max = 0;
for (int i = 0; i < N; i++)
if (max < lis[i])
max = lis[i];
// return size of array minus length of LIS
// as final result
return (N - max);
}
// Driver code to test above methods
public static void main (String[] args)
{
int arr[] = {2, 3, 5, 1, 4, 7, 6};
int N = arr.length;
System.out.println(minInsertionStepToSortArray(arr, N));
}
}
/* This code is contributed by Harsh Agarwal */
Python 3
# Python3 program to get minimum number # of insertion steps to sort an array # method returns min steps of insertion # we need to perform to sort array 'arr' def minInsertionStepToSortArray(arr, N): # lis[i] is going to store length # of lis that ends with i. lis = [0] * N # Initialize lis values for all indexes for i in range(N): lis[i] = 1 # Compute optimized lis values in # bottom up manner for i in range(1, N): for j in range(i): if (arr[i] >= arr[j] and lis[i] < lis[j] + 1): lis[i] = lis[j] + 1 # The overall LIS must end with of the array # elements. Pick maximum of all lis values max = 0 for i in range(N): if (max < lis[i]): max = lis[i] # return size of array minus length # of LIS as final result return (N - max) # Driver Code if __name__ == "__main__": arr = [2, 3, 5, 1, 4, 7, 6] N = len(arr) print (minInsertionStepToSortArray(arr, N)) # This code is contributed by ita_c
C#
// C# program to get minimum number of
// insertion steps to sort an array
using System;
class GfG {
// method returns min steps of insertion
// we need to perform to sort array 'arr'
static int minInsertionStepToSortArray(
int []arr, int N)
{
// lis[i] is going to store length
// of lis that ends with i.
int[] lis = new int[N];
/* Initialize lis values for all
indexes */
for (int i = 0; i < N; i++)
lis[i] = 1;
/* Compute optimized lis values in
bottom up manner */
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] >= arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* The overall LIS must end with of
the array elements. Pick maximum
of all lis values */
int max = 0;
for (int i = 0; i < N; i++)
if (max < lis[i])
max = lis[i];
// return size of array minus length
// of LIS as final result
return (N - max);
}
// Driver code to test above methods
public static void Main (String[] args)
{
int []arr = {2, 3, 5, 1, 4, 7, 6};
int N = arr.Length;
Console.Write(
minInsertionStepToSortArray(arr, N));
}
}
// This code is contributed by parashar.
PHP
<?php
// PHP program to get minimum
// number of insertion steps
// to sort an array
// method returns min steps of
// insertion we need to perform
// to sort array 'arr'
function minInsertionStepToSortArray($arr, $N)
{
// lis[i] is going to store
// length of lis that ends with i.
$lis[$N] = 0;
/* Initialize lis values
for all indexes */
for ($i = 0; $i < $N; $i++)
$lis[$i] = 1;
/* Compute optimized lis values
in bottom up manner */
for ($i = 1; $i < $N; $i++)
for ($j = 0; $j < $i; $j++)
if ($arr[$i] >= $arr[$j] &&
$lis[$i] < $lis[$j] + 1)
$lis[$i] = $lis[$j] + 1;
/* The overall LIS must end with
of the array elements. Pick
maximum of all lis values */
$max = 0;
for ($i = 0; $i < $N; $i++)
if ($max < $lis[$i])
$max = $lis[$i];
// return size of array minus
// length of LIS as final result
return ($N - $max);
}
// Driver code
$arr = array(2, 3, 5, 1, 4, 7, 6);
$N = sizeof($arr) / sizeof($arr[0]);
echo minInsertionStepToSortArray($arr, $N);
// This code is contributed by nitin mittal
?>
Javascript
<script>
// Javascript program to get minimum number of insertion
// steps to sort an array
// method returns min steps of insertion we need
// to perform to sort array 'arr'
function minInsertionStepToSortArray(arr,N)
{
// lis[i] is going to store length of lis
// that ends with i.
let lis = new Array(N);
/* Initialize lis values for all indexes */
for (let i = 0; i < N; i++)
{
lis[i] = 1;
}
/* Compute optimized lis values in bottom up manner */
for (let i = 1; i < N; i++)
{
for (let j = 0; j < i; j++)
{
if (arr[i] >= arr[j] && lis[i] < lis[j] + 1)
{
lis[i] = lis[j] + 1;
}
}
}
/* The overall LIS must end with of the array
elements. Pick maximum of all lis values */
let max = 0;
for (let i = 0; i < N; i++)
{
if (max < lis[i])
{
max = lis[i];
}
}
// return size of array minus length of LIS
// as final result
return (N - max);
}
// Driver code to test above methods
let arr = new Array(2, 3, 5, 1, 4, 7, 6);
let N = arr.length;
document.write(minInsertionStepToSortArray(arr, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
3
Este artículo es una contribución de Utkarsh Trivedi . 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 review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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