Orden de inserción en Java

1. Información general

En este tutorial, discutiremos el algoritmo de ordenación por inserción y veremos su implementación de Java .

La ordenación por inserción es un algoritmo eficaz para ordenar una pequeña cantidad de elementos. Este método se basa en la forma en que los jugadores de cartas clasifican una mano de cartas.

Comenzamos con una mano izquierda vacía y las cartas colocadas sobre la mesa. Luego retiramos una tarjeta a la vez de la mesa y la insertamos en la posición correcta en la mano izquierda. Para encontrar la posición correcta para una nueva carta, la comparamos con el conjunto de cartas ya ordenado en la mano, de derecha a izquierda.

Comencemos por comprender los pasos del algoritmo en forma de pseudocódigo.

2. Pseudocódigo

Vamos a presentar nuestro pseudocódigo para la ordenación por inserción como un procedimiento llamado INSERTION-SORT , tomando como parámetro una matriz A [1 .. n] de n elementos a ordenar. El algoritmo ordena la matriz de entrada en el lugar (reorganizando los elementos dentro de la matriz A).

Una vez finalizado el procedimiento, la matriz de entrada A contiene una permutación de la secuencia de entrada pero en orden ordenado:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Repasemos brevemente el algoritmo anterior.

El índice i indica la posición del elemento actual en la matriz a procesar.

Comenzamos desde el segundo elemento ya que, por definición, se considera que una matriz con un elemento está ordenada. El elemento en el índice i se llama clave . Una vez que se tiene la clave, la segunda parte del algoritmo se ocupa de encontrar su índice correcto. Si la clave es menor que el valor del elemento en el índice j , entonces la clave se mueve una posición hacia la izquierda. El proceso continúa hasta el caso en el que llegamos a un elemento más pequeño que la clave.

Es importante notar que antes de comenzar la iteración para encontrar la posición correcta de la clave en el índice i , la matriz A [1 .. j - 1] ya está ordenada .

3. Implementación imperativa

Para el caso imperativo, vamos a escribir una función llamada insertionSortImperative , tomando como parámetro un arreglo de enteros. La función comienza a iterar sobre la matriz desde el segundo elemento.

En cualquier momento durante la iteración, podríamos pensar que esta matriz está dividida lógicamente en dos porciones; el lado izquierdo es el ordenado y el lado derecho contiene los elementos aún no ordenados.

Una nota importante aquí es que después de encontrar la posición correcta en la que insertaremos el nuevo elemento, desplazamos (y no intercambiamos) los elementos hacia la derecha para liberar un espacio para él.

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }
    

A continuación, creemos una prueba para el método anterior:

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

La prueba anterior demuestra que el algoritmo ordena correctamente en orden ascendente la matriz de entrada .

4. Implementación recursiva

La función para el caso recursivo se llama insertionSortR ecursive y acepta como entrada una matriz de enteros (lo mismo que para el caso imperativo).

La diferencia aquí con el caso imperativo (a pesar de que es recursivo) es que llama a una función sobrecargada con un segundo argumento que es igual al número de elementos para ordenar.

Como queremos ordenar la matriz completa, pasaremos una cantidad de elementos igual a su longitud:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

El caso recursivo es un poco más desafiante. El caso base ocurre cuando intentamos ordenar una matriz con un elemento. En este caso, no hacemos nada.

Todas las llamadas recursivas posteriores ordenan una parte predefinida de la matriz de entrada, comenzando desde el segundo elemento hasta que llegamos al final de la matriz:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

Y así es como se ve la pila de llamadas para una matriz de entrada de 6 elementos:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Veamos también la prueba para ello:

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

La prueba anterior demuestra que el algoritmo ordena correctamente en orden ascendente la matriz de entrada .

5. Complejidad temporal y espacial

El tiempo que tarda el procedimiento INSERTION-SORT en ejecutarse es O (n ^ 2) . Para cada nuevo elemento, iteramos de derecha a izquierda sobre la parte ya ordenada de la matriz para encontrar su posición correcta. Luego lo insertamos desplazando los elementos una posición a la derecha.

El algoritmo ordena en su lugar, por lo que su complejidad espacial es O (1) para la implementación imperativa y O (n) para la implementación recursiva.

6. Conclusión

En este tutorial, vimos cómo implementar la ordenación por inserción.

Este algoritmo es útil para clasificar una pequeña cantidad de elementos. Se vuelve ineficaz cuando se ordenan secuencias de entrada que tienen más de 100 elementos.

Tenga en cuenta que a pesar de su complejidad cuadrática, se ordena en su lugar sin la necesidad de espacio auxiliar, como es el caso de la ordenación por combinación .

El código completo se puede encontrar en GitHub.