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)

    Primer intento0,000058
    Segunda ejecuci贸n0,000085
    Tercera carrera0,000073
    Cuarta carrera0,000060
    Quinta carrera0,000073

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

    Primer intento0.091
    Segunda ejecuci贸n0,125
    Tercera carrera0.104
    Cuarta carrera0.108
    Quinta carrera0,123

    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).!

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *