Ordenación por inserción en Java

La clasificación por inserción es un algoritmo de clasificación simple que funciona de maravilla en matrices pequeñas. A menudo se usa junto con Quicksort y Merge Sort en las etapas finales. En este artículo, implementaremos la ordenación por inserción en Java.

Introducción

La clasificación es un aspecto crucial de la digestión de datos. Para nosotros, los humanos, es mucho más natural ordenar las cosas que tienen algo en común como la fecha de publicación, el orden alfabético, los artículos que pertenecen a un autor, de menor a mayor, etc. Esto hace que sea mucho más fácil comprender el datos ya que están lógicamente conectados en lugar de dispersos por todas partes.

E igualmente importante, las matrices ordenadas son más fáciles de usar para las computadoras. Por ejemplo, una matriz ordenada se puede buscar mucho más rápido, como con el algoritmo búsqueda binaria, que se ejecuta en tiempo O(logn). Un algoritmo como este simplemente no funciona sin una matriz ordenada.

Clasificación por inserción

Insertion Sort es uno de los algoritmos de clasificación más simples, que funciona considerablemente más rápido en colecciones más pequeñas que el introductorio Ordenamiento de burbuja e incluso Selection Sort a pesar de que son todos los algoritmos cuadráticos simples (O(n^2^).

Es genial para colecciones pequeñas y casi ordenadas (~10 elementos) lo que lo hace extremadamente útil cuando se usa en combinación con otros algoritmos de clasificación más avanzados como Quicksort u [Ordenar por fusión](/fusionar-ordenacion-en- Java/). La implementación oficial sort() de Java de Collections API usó un Dual Pivot Quicksort, aunque recurrió a Insertion Sort para colecciones de tamaño 7.

Por lo general, se implementa de forma imperativa (aunque también puede ser recursivo) y representa un algoritmo estable y in situ que funciona de maravilla en conjuntos de datos pequeños.

Esto significa que conserva el orden relativo de los elementos duplicados después de la clasificación (in situ) y no requiere ninguna memoria adicional para clasificar con una complejidad de espacio constante O(1) (estable).

La clasificación por inserción funciona de manera muy similar a como los humanos clasifican las cartas en sus manos al dividir la colección en dos partes: clasificadas y sin clasificar.

Luego atraviesa la partición sin ordenar e inserta cada elemento en su lugar relativo correcto en la matriz ordenada.

Aquí hay una representación visual de cómo funciona:

insertion sort gif

Si esto no tiene mucho sentido ahora, se explica paso a paso en la implementación a continuación junto con el código.

Implementación

Dicho esto, sigamos adelante e implementemos el algoritmo en matrices enteras primitivas y una colección de objetos con un método compareTo() personalizado para definir los criterios de comparación.

También podríamos implementar la interfaz Comparable y anular el método compareTo() para definir los criterios de comparación y usar la Collections API, simplemente llamando al método sort() proporcionado allí. Sin embargo, de esa manera, no implementamos nuestra propia lógica de clasificación.

Clasificación de matrices {#clasificación de matrices}

La clasificación de matrices de enteros primitivos es rápida y sencilla mediante la clasificación por inserción:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public static void insertionSort(int array[]) {
    for (int j = 1; j < array.length; j++) {
        int current = array[j];
        int i = j-1;
        while ((i > -1) && (array[i] > current)) {
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = current;
    }
}

La iteración comienza en el segundo elemento (el primero se considera ordenado de manera predeterminada) y compara el primer elemento de la matriz no ordenada con el último elemento de la matriz ordenada.

El elemento no ordenado se "guarda" en la variable actual y si el elemento más alto en la matriz ordenada es más grande que la variable actual, la porción adecuada de la matriz ordenada se desplaza a la derecha.

Tenga en cuenta que no se intercambian, se desplaza hacia la derecha y ahora tanto array[j] (al que se accede a través de array[i+1]) como array[i] tienen el mismo valor .

Luego, independientemente de si una parte de la matriz ordenada se desplaza hacia la derecha, establecemos la matriz [j] en actual, insertando efectivamente el entero protegido en su lugar correcto.

Si el elemento actual no es más pequeño que el elemento ordenado más grande (es decir, es más grande), simplemente se inserta al final donde pertenece.

Avancemos y completemos una pequeña matriz de enteros y luego clasifíquelos:

1
2
3
int[] array = new int[]{1, 7, 5, 6, 9, 4, 2, 3};
insertionSort(array);
System.out.println(Arrays.toString(array));

Ejecutar este fragmento de código producirá:

1
[1, 2, 3, 4, 5, 6, 7, 9]

Clasificación de ArrayLists

Ordenar una ArrayList es un ejemplo más práctico/del mundo real que probablemente encontrará mucho más a menudo que los números enteros primitivos.

Ya que estamos clasificando objetos según ciertos criterios, primero definamos una clase para nuestro Elemento de una colección:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

    // Getters and setters

    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res = -1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

Contiene un método compareTo() que acepta otro Elemento para compararlo. En esta implementación mundana, se comparan sus ids, aunque aquí es donde puede ser creativo.

Reelaboremos el algoritmo para ordenar estos objetos en su lugar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public static void insertionSortArrayList(List<Element> list) {
    for (int j = 1; j < list.size(); j++) {
        Element current = list.get(j);
        int i = j-1;
        while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
            list.set(i+1, list.get(i));
            i--;
        }
        list.set(i+1, current);
    }
}

No ha cambiado mucho, espere usar los métodos proporcionados por una Lista y comparar los elementos con nuestro método personalizado compareTo(). Aquí, verificamos si el resultado de la comparación es 1, ya que eso significa que el primer elemento es más grande que el segundo, como se define en nuestro método.

Ahora, llenemos una ArrayList con algunos elementos y mezclemos:

1
2
3
4
5
6
7
8
9
List<Element> list = new ArrayList<>();

// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}

// Move the elements to a random order
Collections.shuffle(list);

Y ahora, ordenemos esa lista:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Print list before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
insertionSortArrayList(list);

System.out.println();

// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));

Este fragmento de código nos dará:

1
2
4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Complejidad del tiempo {#complejidad del tiempo}

La complejidad de tiempo, tanto la media como la peor del tipo de inserción, es O(n^2^), que es bastante terrible. Hay complejidades de tiempo mucho mejores disponibles a través de otros algoritmos de clasificación más avanzados, aunque lo que hace que la clasificación por inserción se destaque es lo rápido que es en colecciones pequeñas y casi ordenadas.

Intentemos cronometrarlo a través de 5 ejecuciones de colecciones pequeñas y 5 ejecuciones de colecciones grandes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
List<Element> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
    list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled list
list.forEach(e -> System.out.print(e.getId() + ", "));

long startTime1 = System.nanoTime();
insertionSort.insertionSortArrayList(list);
long endTime1 = System.nanoTime();

// Print sorted collection
list.forEach(e -> System.out.print(e.getId() + ", "));
System.out.println();

// Print runtime in nanoseconds
System.out.println("Insertion Sort runtime: " + (endTime1 - startTime1));

Clasificación por inserción (10) veces Primera ejecución 0.000058 Segunda ejecución 0.000085 Tercera Ejecución 0.000073 Cuarta Ejecución 0.000060 Quinta ejecución 0.000073



Clasificación por inserción (10k) veces Primera ejecución 0.091 Segunda ejecución 0.125 Tercera carrera 0.104 Cuarta Corrida 0.108 Quinta carrera 0.123


Comparado con Bubble Sort que tiene la misma complejidad de tiempo, Insertion Sort es ~5 veces más rápido.

Conclusión

Ordenación por inserción es uno de los algoritmos de clasificación más simples, que funciona considerablemente más rápido en colecciones más pequeñas que la Clasificación por burbuja introductoria e incluso la Clasificación por selección, aunque todos son algoritmos cuadráticos simples (O(n^2^).

Es excelente para colecciones pequeñas y casi ordenadas (~10 elementos), lo que lo hace extremadamente útil cuando se usa en combinación con otros algoritmos de clasificación más avanzados, como Quicksort o Merge Sort.

Por lo general, se implementa de forma imperativa (aunque también puede ser recursivo) y representa un algoritmo estable y in situ que funciona de maravilla en conjuntos de datos pequeños.

Esto significa que conserva el orden relativo de los elementos duplicados (in situ) y no requiere ninguna memoria adicional para ordenar con una complejidad de espacio constante O(1) (estable). ble).