Todo lo que necesita saber sobre el algoritmo de ordenación por inserción

Introducción

¡Hola! Soy Sanjula, y en esta guía espero enseñarte un poco sobre el algoritmo de ordenación por inserción, que incluye:

  • ¿Qué es el tipo de inserción?
  • ¿Por qué es importante el tipo de inserción?
  • Rendimiento de la ordenación por inserción
  • ¿Cómo funciona la ordenación por inserción?
  • Implementación Java de ordenación por inserción

¡Empecemos!

¿Qué es el tipo de inserción?

Es un algoritmo de clasificación simple que clasifica una matriz un elemento a la vez.

¿Por qué es importante el tipo de inserción?

La clasificación por inserción tiene varias ventajas que incluyen:

  • La pura simplicidad del algoritmo.
  • El orden relativo de los elementos con claves iguales no cambia.
  • La capacidad de ordenar una lista a medida que se recibe.
  • Eficiente para conjuntos de datos pequeños, especialmente en la práctica que otros algoritmos cuadráticos, es decir, O (n²).
  • Solo requiere una cantidad constante de espacio de memoria adicional: O (1).

Rendimiento de la ordenación por inserción

  • El peor rendimiento de la ordenación por inserción es O (n²) comparaciones y cambios.
  • El rendimiento en el mejor de los casos son las comparaciones O (n) y los intercambios O (1).
  • El rendimiento promedio de casos es O (n²) comparaciones e intercambios.

¿Cómo funciona la ordenación por inserción?

En cada iteración, la ordenación por inserción compara el elemento actual con el siguiente elemento y determina si el elemento actual es mayor que el que se comparó.

Si esto es cierto , deja el elemento en su lugar y pasa al siguiente elemento. Si es falso , entonces encuentra su posición correcta en la matriz ordenada y la mueve a esa posición desplazando todos los elementos que son más grandes en la matriz ordenada a una posición adelante.

Implementación Java de ordenación por inserción

PD: ¡Primero intenta implementarlo por tu cuenta!

¡¡¡Felicidades!!! Ahora ha absorbido el conocimiento básico pero esencial sobre cómo funciona la ordenación por inserción.

Para referencias o informes de problemas relacionados con el código anterior, use el siguiente enlace público de GitHub Gist.

Espero que esto haya sido útil. ¡Gracias por leer! :)