Introducción a los algoritmos de ordenación (ordenación por inserción)
Se basa en que, en cada iteración, tomamos un elemento de la lista y lo insertamos en su posición correcta dentro de la parte ya ordenada, de ahí su nombre.
En realidad lo que hace es que con cada elemento se compara con los elementos anteriores y lo mueves hasta su posición correcta. Este algoritmo también es un in-place (recordemos que es aquel en el que la ordenación se produce dentro de la misma estructura de datos entrante).
Aquí un ejemplo:
function insertionSort(&$elements): void
{
$length = count($elements);
for ($currentIndex = 1; $currentIndex < $length; $currentIndex++) {
$currentValue = $elements[$currentIndex];
$indexToCompare = $currentIndex - 1;
while ($indexToCompare >= 0 && $elements[$indexToCompare] > $currentValue) {
$elements[$indexToCompare + 1] = $elements[$indexToCompare];
$indexToCompare--;
}
$elements[$indexToCompare + 1] = $currentValue;
}
}
Este código ordena una lista de menor a mayor creando una zona ordenada al principio. Vamos a poner la siguiente lista de elementos para ordenar: [4,2,3,1] y que devuelva [1,2,3,4].
Primera iteración
Empezamos por la primera iteración
$length=4
El índice actual empieza en 1 porque entendemos que el primer elemento ya está aparentemente ordenado $currentIndex=1. El valor actual empieza en el 2: $currentValue=2
$indexToCompare=0 (El índice del elemento anterior).
Veamos si cumple la condición:
while ($indexToCompare >= 0 && $elements[$indexToCompare] > $currentValue)
Esto se cumple porque $indexToCompare vale 0 y 4 >2 se cumple, quedando la lista en [4,4,3,1].
$indexToCompare disminuye en 1 $indexToCompare=-1 y ya no cumple con la condición de dentro del while.
Entonces el $currentValue lo situamos en primera posición ( $elements[$indexToCompare + 1] = $currentValue;) quedando: [2,4,3,1].
Segunda iteración
Vamos por la siguiente iteración desde el principio, $currentIndex=2 $currentValue=3
$indexToCompare=1
while ($indexToCompare >= 0 && $elements[$indexToCompare] > $currentValue)
El $indexToCompare es 1 y 4>3 por lo que entra dentro del while quedando [2,4,4,1] e $indexToCompare=0 , pero no entra otra vez en el while por la segunda condición, dado que no se cumple 2>3.
Y ponemos el valor actual en el elemento anterior quedando: [2,3,4,1].
Tercera iteración
Vamos a la última pasada, $currentIndex=3
$currentValue=1 $indexToCompare=2
Vemos que cumple el buckle while ($indexToCompare >0 y 4 >1 ) lo cumple y queda [2,3,4,4]. $indexToCompare=1 y cumple el while (3>1) y queda: [2,3,3,4] e $indexToCompare=0
y vuelve a cumplir el while (2>1) y queda [2,2,3,4] $indexToCompare vale -1 y ya no entra en el bucle y ponemos el $currentValue en la posición inicial quedando como resultado final: [1,2,3,4] ya que hemos recorrido todas las pasadas.
La ordenación por inserción se hace realmente eficaz en conjuntos pequeños de datos o en listas casi ordenadas, donde puede comportarse de forma casi lineal. Su eficiencia se reduce cuando el elemento más grande se encuentra al principio del conjunto, ya que el bucle interno debe desplazar casi todos los elementos anteriores para insertarlo en su posición correcta.
SpectrumGirl <3 Mastodon me



Empezó en el mundo del folk y fue trabajando su carrera en grupos y era conocida por su humor y optimismo y era conocida como la más carismática del grupo que finalmente culminó en la canción “California Dreamin' “.
Finalmente durante la separación del grupo tuvo una carrera relevante como solista y llegó a actuar en Las Vegas y llegó a tener papeles en películas.