Ordenación por inserción en Java

Ordenar arreglos es una de las operaciones más comunes que un principiante de Java debería saber hacer. Aunque las matrices no siempre son la forma más conveniente de organizar los datos y esto se aplica principalmente a números pequeños, el concepto detrás de la clasificación de matrices tiene toneladas de aplicaciones en software complejo y ciencia de datos. En esta publicación, veremos más de cerca qué es el ordenamiento por inserción. Incluimos algunos ejemplos y problemas de práctica para ayudarlo a familiarizarse completamente con este concepto.

¿Qué es la ordenación por inserción?

Básicamente, la ordenación por inserción es un algoritmo que usan los desarrolladores para organizar cadenas de números pequeños. Divide todos los valores en dos pilas: una ordenada y otra sin ordenar. Uno por uno, los números de la pila "sin ordenar" se seleccionan y se colocan en el orden correcto. Echemos un vistazo más de cerca a la entrada y la salida del ordenamiento por inserción:

• Entrada: una matriz A con elementos numéricos no ordenados: A[0,1, n, n-2...].
• Salida: una matriz que contiene los mismos números pero completamente ordenada. Este se suele denominar B: B[0]B[1]...B[n-1].

Hay varias formas de utilizar la ordenación por inserción; estas son las más populares:

• Clasificación numérica (orden creciente): [1, 2, 3, 4, 5]
• Clasificación numérica (orden decreciente): [5, 4, 3, 2, 1]
• Clasificación alfabética: [a, b, c, d]

Nota: si tiene una matriz vacía o un singleton, estos se consideran ordenados de manera predeterminada.

Comprender la teoría de la ordenación por inserción

Antes de explorar el código detrás de la ordenación por inserción, analicemos el algoritmo utilizando un lenguaje no técnico. Debido a que mostraremos el código para clasificar en orden ascendente, tiene sentido explicar el algoritmo paso a paso en esta publicación. Paso 1. Iterar entre arr[1]y arr[n]dónde nes un valor numérico generalmente menor que 10. Paso 2. Comparar el elemento que eligió (conocido como key) con el número anterior en la secuencia usando el sort()método. Paso 3. Si todos los elementos son más pequeños que sus sucesores, repite la comparación hasta que encuentres un valor mayor. Paso 4. Intercambie un valor mayor una posición más allá del menor para crear una secuencia ordenada. Paso 5. Repite el proceso hasta que obtengas una cadena ordenada de caracteres

Ordenar matrices primitivas

Dado que el algoritmo es una de las operaciones de Java más sencillas, incluso los principiantes no deberían tener muchos problemas para implementarlo. Aquí hay una guía paso a paso para ordenar una matriz

1. Declarar una matriz para la clasificación

Para empezar, creemos una cadena de valores que luego mostraremos usando Java. Para usar la ordenación por inserción, debe crear una matriz. Para eso, usaint[]

int[] arrayA = {10, 14, 20, 30};

2. Usa sort_arr para implementar el algoritmo

El método sort_arr es una de las formas más comunes de implementar la ordenación por inserción. En la práctica, se ve así:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Crea un bucle y un iterador

Mediante el uso de un bucle en el algoritmo de clasificación por inserción, los desarrolladores no tienen que repetir la lógica para cada elemento. Aunque la creación de bucles parece compleja, es bastante simple. He aquí un ejemplo:

for(int i=0; i< sort_arr.length; ++i){

Ahora que tiene un bucle en funcionamiento, es hora de crear un iterador que ordenará todos los elementos en el orden deseado. De ahora en adelante, nos referiremos al iterador como " j".

        int j = i;

4. Crear un "bucle while"

Cuando se trata de ordenar por inserción, un ciclo "while" es esencial para una nueva matriz ordenada. Para configurarlo para una clasificación de inserción de orden ascendente, un desarrollador debe cumplir con dos condiciones:

• El valor asignado a j tiene que ser mayor que 0
• El valor asignado a j-1debe ser mayor que el jíndice

Tan pronto como ambas condiciones en el ciclo while sean verdaderas, el valor clave de la matriz será igual al jíndice.

5. Ordenar la matriz

Después de configurar el ciclo while, los valores jy j-1se intercambiarán hasta que una o ambas condiciones en el ciclo while fallen. De manera similar, la clasificación se repetirá para cada valor en el bucle for hasta que las condiciones del bucle for fallen también. Así es como funciona el proceso de clasificación por inserción en la práctica:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Ordenar una ArrayList

Si bien es importante comprender las matemáticas detrás de la ordenación por inserción, cuando se trata del desarrollo de software de la vida real, ordenará ArrayLists mucho más que secuencias en matrices primitivas. Aquí hay una guía paso a paso para ordenar una ArrayList:

1. Cree una nueva Elementclase para los elementos que pertenecen a la colección.

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

2. Dentro de una colección, hay un compareTo()método: lo usaremos para comparar los identificadores de dos elementos.

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

3. Aplique el algoritmo y cree algunos bucles para ordenar los objetos ArrayListen lugar de compararlos.

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

4. ArrayListTambién puede agregar más elementos , como se muestra a continuación:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. Ahora es el momento de ordenar:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. Ahora comparemos la entrada y la salida para asegurarnos de que no cometimos errores. Aquí está la comparación de la cadena que usamos como ejemplo.

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

Problemas de práctica de clasificación por inserción

Ahora que domina este algoritmo de clasificación, es hora de poner a prueba sus habilidades teóricas y prácticas. Cuestionario de teoría n.° 1 Se le proporciona una matriz [1, 4, 6, 8] y se le agrega un nuevo elemento n = 7. ¿Cuál es el número de comparaciones que necesitará hacer para obtener una secuencia ordenada de números? Indique el valor final del índice n en la matriz. Cuestionario de teoría n.° 2 En una entrevista de trabajo, el líder de un equipo le pide que demuestre que la inserción de clasificación es un método ineficiente. Dada una cadena numérica de [0, 3, 6, 8, 9], ¿cuál debería ser el orden de su secuencia de entrada para maximizar el tiempo de ejecución requerido para clasificar? Problema de práctica Ordene la matriz [0, 1, 4, 5, 2, 3, 7, 9, 8] en orden ascendente utilizando la ordenación por inserción para Java.

Conclusión

El mayor desafío para comprender la ordenación por inserción es comprender cómo funciona el proceso. Una vez que lo domine, convertir la plantilla en código es pan comido. Siempre que practique y revise problemas de práctica relevantes con el tiempo, mejorará rápidamente su velocidad de ordenación por inserción.