Guía para el algoritmo de clasificación in situ que funciona con una implementación de Java

1. Introducción

En este tutorial, explicaremos cómo funciona el algoritmo de clasificación in situ.

2. Algoritmos in situ

Los algoritmos in situ son aquellos que no necesitan ninguna estructura de datos auxiliares para transformar los datos de entrada. Básicamente, significa que el algoritmo no usa espacio adicional para la manipulación de entrada. Prácticamente anula la entrada con la salida.

Sin embargo, en realidad, el algoritmo puede requerir un espacio adicional pequeño y no constante para las variables auxiliares. La complejidad de este espacio es en la mayoría de los casos O (log n) , aunque a veces se permite algo menos que lineal.

3. Pseudocódigo

Veamos ahora un pseudocódigo y comparemos el algoritmo en el lugar con el fuera de lugar.

Asumiremos que queremos invertir una matriz de n números.

3.1. Algoritmo in situ

Si pensamos en el problema, veremos que tenemos una matriz de entrada y una matriz invertida como salida. Al final, en realidad no necesitamos nuestra matriz original, solo la inversa.

Entonces, ¿por qué no sobrescribiríamos la entrada en lugar de mover sus valores a la matriz completamente nueva, ya que podría parecer el método más obvio? Para hacer eso, solo necesitaremos una variable adicional para almacenar temporalmente los valores con los que estamos trabajando actualmente:

reversInPlace(array A[n]) for i from 0 to n/2 temp = A[i] A[i] = A[n - 1 - i] A[n - 1 - i] = temp

Vale la pena mencionar que no importa cuán grande sea la matriz, el espacio extra que necesitamos siempre será O (1) en este caso.

La ilustración muestra que necesitamos menos pasos que en el caso anterior:

3.2. Algoritmo fuera de lugar

Por otro lado, también podemos hacer esto de una manera bastante simple y más obvia. Podemos crear una nueva matriz del mismo tamaño, copiar los valores del original en el orden correspondiente y luego eliminar la matriz original:

reverseOutOfPlace(array A[n]) create new array B[n] for i from 0 to n - 1 B[i] = A[i] delete A return B

Aunque esto hará lo que queríamos que hiciera, no es lo suficientemente eficiente. Tenemos O (n) espacio adicional requerido ya que tenemos dos matrices para manipular . Además de eso, crear y eliminar una nueva matriz suele ser una operación lenta.

Veamos la ilustración del proceso:

4. Implementación de Java

Veamos ahora cómo podemos implementar en Java lo que aprendimos en la sección anterior.

En primer lugar, implementaremos un algoritmo in situ:

public static int[] reverseInPlace(int A[]) { int n = A.length; for (int i = 0; i < n / 2; i++) { int temp = A[i]; A[i] = A[n - 1 - i]; A[n - 1 - i] = temp; } return A; }

Podemos probar fácilmente que esto funciona como se esperaba:

@Test public void givenArray_whenInPlaceSort_thenReversed() { int[] input = {1, 2, 3, 4, 5, 6, 7}; int[] expected = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals("the two arrays are not equal", expected, InOutSort.reverseInPlace(input)); }

En segundo lugar, veamos la implementación del algoritmo fuera de lugar:

public static int[] reverseOutOfPlace(int A[]) { int n = A.length; int[] B = new int[n]; for (int i = 0; i < n; i++) { B[n - i - 1] = A[i]; } return B; }

La prueba es bastante sencilla:

@Test public void givenArray_whenOutOfPlaceSort_thenReversed() { int[] input = {1, 2, 3, 4, 5, 6, 7}; int[] expected = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals("the two arrays are not equal", expected, InOutSort.reverseOutOfPlace(input)); }

5. Ejemplos

Hay muchos algoritmos de clasificación que utilizan un enfoque in situ. Algunos de ellos son el ordenamiento por inserción, el ordenamiento por burbujas, el ordenamiento por montón, el ordenamiento rápido y el ordenamiento por shell, y puede obtener más información sobre ellos y comprobar sus implementaciones de Java.

Además, debemos mencionar la clasificación en peine y la clasificación en pilas. Todos estos tienen complejidad espacial O (log n) .

También podría ser útil aprender más sobre la teoría de la notación Big-O, así como ver algunos ejemplos prácticos de Java sobre la complejidad del algoritmo.

6. Conclusión

En este artículo, describimos los llamados algoritmos in situ, ilustramos cómo funcionan usando pseudocódigo y algunos ejemplos, enumeramos varios algoritmos que funcionan con este principio y finalmente implementamos los ejemplos básicos en Java.

Como de costumbre, el código completo se puede encontrar en GitHub.