Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

En su núcleo, la ordenación por inserción sirve como un algoritmo de ordenación. Puede colocar varios elementos no ordenados en los lugares más adecuados para ellos en cada iteración. Sería justo decir que este algoritmo funciona de forma bastante similar a cómo la gente ordena las cartas en sus manos. Si tiene experiencia en juegos de cartas, sabrá que los jugadores de cartas ordenan con la suposición de que las primeras cartas ya están ordenadas, tras lo cual seleccionan las no ordenadas.

En caso de que la carta sin clasificar resulte ser más grande que la carta en la mano de los jugadores, tienen que colocarla a la derecha. En caso contrario, tienen que dejar la carta a la izquierda. Del mismo modo, tienen que colocar el resto de las cartas sin clasificar y mantenerlas en sus respectivos lugares. El enfoque utilizado por la ordenación por inserción es bastante similar a este.

Los fundamentos de cómo funciona la ordenación por inserción

A continuación se mencionan tres pasos que le darán una idea de cómo funciona la ordenación por inserción:

  • En el primer paso, los elementos en cuestión se comparan con los elementos adyacentes a ellos
  • Si cada comparación muestra que el elemento en cuestión puede ser utilizado en una posición específica, entonces se hace un espacio para él. Para ello, se desplaza la posición de los demás elementos hacia la derecha.
  • Este procedimiento continúa hasta que todos los elementos presentes en la matriz encuentran su posición correcta

Características de la ordenación por inserción

Aunque este algoritmo de ordenación por inserción tiene una amplia gama de características, hay tres importantes con las que todo el mundo debe familiarizarse.

  • En primer lugar, el algoritmo de ordenación por inserción es increíblemente sencillo. Algunos dirían incluso que es el más simple que existe debido a su sencilla implementación
  • Si eres un programador que trabaja con valores de datos pequeños con regularidad, el uso de este algoritmo te resultará muy útil.
  • La naturaleza del algoritmo de ordenación por inserción es bastante adaptable, lo que lo hace ideal para conjuntos de datos parcialmente ordenados

Preguntas comunes sobre la ordenación por inserción

Esta es una lista de respuestas concisas a preguntas comunes sobre los algoritmos de ordenación por inserción.

¿Qué son los casos límite del algoritmo de ordenación por inserción?

La ordenación por inserción requiere una gran cantidad de tiempo cuando se trata de ordenar elementos que están en orden inverso. Sin embargo, si los elementos ya están ordenados, no requerirá mucho tiempo.

¿Son estables los algoritmos de ordenación por inserción?

Los algoritmos de ordenación por inserción son increíblemente estables, especialmente si se comparan con otros algoritmos.

¿Cuándo es el mejor momento para utilizar el algoritmo de ordenación por inserción?

Como se mencionó anteriormente, la ordenación por inserción se utiliza a menudo cuando hay una pequeña cantidad de elementos. Dicho esto, también puede ser muy útil cuando un array de entrada no necesita demasiada ordenación y sólo tiene unos pocos elementos mal colocados.

¿Qué enfoque sigue la ordenación por inserción?

El enfoque que sigue el algoritmo de ordenación por inserción es incremental, por lo que es increíblemente popular entre los programadores que ordenan arrays.

Explicación de la ordenación por inserción binaria

Los programadores pueden utilizar la búsqueda binaria para reducir la cantidad de comparaciones presentes en la ordenación por inserción regular. La ordenación por inserción binaria utiliza la búsqueda para encontrar el lugar ideal para insertar el elemento elegido en cada iteración. Cuando se trata de la inserción regular, la ordenación utiliza O(i) (en la i-ésima iteración) durante el peor de los casos.
Podemos utilizar la investigación binaria para reducirlo a O(logi). Dicho esto, sin embargo, el algoritmo sigue teniendo un tiempo de ejecución alrededor de O(n^2) para los peores casos. Esto se debe a la cantidad de intercambios necesarios por inserción.

Pasos para implementar la ordenación por inserción en listas enlazadas

Los pasos mencionados a continuación muestran cómo se puede hacer uso del algoritmo de ordenación por inserción en una lista enlazada.

  • Empieza por crear una lista ordenada, asegurándote de que está vacía
  • Recorra la lista creada y siga este paso para cada nodo
  • Introduzca el nodo actual en forma de resultado o lista ordenada
  • Finalmente, cambie la cabeza de la lista enlazada, convirtiéndola en cabeza de la lista ordenada, también conocida como lista de resultados

Las principales aplicaciones de la ordenación por inserción

Aquí hay dos de los escenarios más comunes cuando los programadores utilizan la ordenación por inserción.

  • En primer lugar, lo utilizan cuando hay un array con pocos elementos
  • La ordenación por inserción también puede ser útil cuando sólo hay un pequeño número de elementos que ordenar.

Complejidades temporales de la ordenación por inserción

A continuación se muestran las complejidades de tiempo que se pueden encontrar en la ordenación por inserción.

Complejidad del peor caso O (n2) – Worst Case Complexity O (n2)
Imagínese que hay un array presente en orden ascendente, que usted planta para ordenar en orden descendente. Un caso como éste da lugar a la complejidad del peor caso. En tal situación, tienes que comparar cada elemento con otros elementos para asegurar que hay (n-1) comparaciones para cada n-ésimo elemento.

La cantidad total de comparaciones será n*(n-1) ~ n2

Complejidad del caso medio O(n) – Average Case Complexity O(n)
Este tipo de complejidad suele darse cuando los elementos de un array están mezclados, es decir, no están ni en orden descendente ni en orden ascendente.

Complejidad espacial – Space Complexity
La complejidad espacial se convierte en 0(1) siempre que haya una implementación de una variable extra.

Complejidad del mejor caso – Best Case Complexity
Siempre que un array no requiera ninguna ordenación, la cantidad de veces que se ejecuta el bucle exterior es n. Por otro lado, el bucle interior permanece inactivo y no realiza ninguna ejecución. Esto significa que la cantidad de comparaciones será n, resultando en una complejidad lineal.

Análisis de la complejidad temporal

Aunque no se puede negar lo eficiente que es la ordenación por inserción, pero si uno proporcionara un array que ya está ordenado, a la ordenación por inserción, el algoritmo seguirá llevando a cabo la otra para el bucle. Esto requerirá n pasos para ordenar un array de los n elementos que ya estaban ordenados para empezar, esencialmente convirtiendo la complejidad de tiempo del mejor caso en una función n lineal.

Un array sin ordenar requiere un elemento para hacer comparaciones con otros elementos, lo que significa que cada elemento de n se compara con otros n elementos. También ayudaría analizar otros algoritmos similares como Quick Sort, Merge Sort o Selection Sort y medir sus respectivas complejidades.