Orden de 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, del más pequeño al más grande, etc. Esto hace que sea mucho más fácil comprender los datos ya que conectados lógicamente en lugar de dispersos por todas partes.

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

Tipo de inserción

La ordenación por inserción es uno de los algoritmos de ordenación más simples, que funciona considerablemente más rápido en colecciones más pequeñas que la ordenación por burbujas introductoria e incluso la ordenación por selección, aunque todos son algoritmos cuadráticos simples (O (n2).

Es ideal 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. Oficial de Java sort() La implementación de la API de colecciones utilizó un Quicksort de doble pivote, aunque se recurrió a Insertion Sort para colecciones de tamaño 7.

Por lo general, se implementa de manera imperativa (aunque también puede ser recursiva) y representa un algoritmo estable en el lugar que funciona de maravilla en pequeños conjuntos de datos.

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

Insertion Sort funciona de manera muy similar a como los humanos clasifican las tarjetas en sus manos dividiendo la colección en dos partes: clasificadas y sin clasificar.

A continuación, atraviesa la partición sin clasificar e inserta cada elemento en su lugar relativo correcto en la matriz ordenada.

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

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 de enteros primitivos y una colección de objetos con un compareTo() método para definir criterios de comparación.

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

Ordenación de matrices

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

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 forma predeterminada) y compara el primer elemento de la matriz no ordenada con el último elemento de la matriz ordenada.

El elemento no clasificado se «guarda» en la variable current y si el elemento más alto en la matriz ordenada es más grande que el current variable: la parte adecuada de la matriz ordenada se desplaza hacia la derecha.

Tenga en cuenta que no se han intercambiado, se ha desplazado a la derecha y ahora ambos array[j] (se accede a través de array[i+1]) y array[i] tienen el mismo valor.

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

Si el current El elemento 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.

Sigamos adelante y completemos una pequeña matriz de números enteros y luego ordénelos:

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, 2, 3, 4, 5, 6, 7, 9]

Ordenar ArrayLists

Clasificando un ArrayList es un ejemplo más práctico / del mundo real que probablemente encontrará con mucha más frecuencia que los enteros primitivos.

Dado que estamos ordenando objetos según ciertos criterios, primero definamos una clase para nuestro Element de una colección:

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 compareTo() método que acepta otro Element para ser comparado. En esta implementación mundana, su idse están comparando, aunque aquí es donde puede ser creativo.

En su lugar, reelaboremos el algoritmo para ordenar estos objetos:

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 utilizar los métodos proporcionados por un List y comparando los elementos con nuestra costumbre compareTo() método. Aquí, comprobamos 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, poblaremos un ArrayList con algunos elementos y mezclarlo:

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:

// 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á:

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

Complejidad del tiempo

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

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

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));

Orden de inserción (10) Hora (s)

Orden de inserción (10k) tiempo (s)

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

Conclusión

La ordenación por inserción es uno de los algoritmos de ordenación más simples, que funciona considerablemente más rápido en colecciones más pequeñas que la ordenación por burbujas introductoria e incluso la ordenación por selección, aunque todos son algoritmos cuadráticos simples (O (n2).

Es ideal 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 manera imperativa (aunque también puede ser recursiva) y representa un algoritmo estable en el lugar que funciona de maravilla en pequeños conjuntos de datos.

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