Este artículo es parte de una serie que abarca los algoritmos de ordenación en JavaScript. Puedes encontrar el resto de la serie aquí. Si eres nuevo en los algoritmos de ordenación, o en los algoritmos en general, lee esto primero para obtener una base sólida para seguir adelante. Hoy cubriré los pormenores del tipo de inserción. La ordenación por inserción es más compleja pero un poco más útil que la ordenación por burbujas. El peor de los casos es similar al de la clasificación de burbujas, pero su mejor caso lo hace adecuado para momentos en los que está bastante seguro de que una lista está casi ordenada o probablemente ya está ordenada. Veamos el panorama general.
La ordenación por inserción funciona observando cada elemento de una lista (empezando por el segundo elemento) y comparándolo con el elemento anterior. Si el elemento anterior es más grande, se intercambian. Esto continúa hasta que el elemento es más pequeño, momento en el que hacemos lo mismo para el siguiente elemento de la lista.
La ordenación por inserción no es tan mala.. siempre y cuando lo uses en las circunstancias adecuadas.
- Es más rápido que la mayoría de los algoritmos de ordenación O(n log n) para listas pequeñas.
- Es extremadamente eficiente en memoria y requiere solo O (1) espacio auxiliar para el elemento individual que se está moviendo.
- Es estable: los elementos iguales aparecen en el mismo orden en la lista ordenada.
- Es adaptable: es rápido al ordenar listas en su mayoría ordenadas o al agregar elementos a una lista ya ordenada.
- ¡Es muy fácil de implementar!
Complejidad
La complejidad temporal de este algoritmo, en el peor de los casos, es cuadrática — O(n2). A medida que n se acerca al infinito, el caso promedio se acerca al peor de los casos dividido por dos. Sin embargo, ya que si su lista está ordenada o casi, puede ser O(n) en el mejor de los casos y, por lo tanto, bien adaptada a ese escenario.
Cuando es rápido
Como se mencionó anteriormente, puede ser rápido en ciertas circunstancias. Considere la matriz, cuando se utiliza un algoritmo como merge sort, todavía tendríamos que dividir todos los elementos y luego fusionarlos de nuevo. Con la clasificación por inserción, solo necesitamos verificar que están en el orden correcto de «ordenados hasta ahora», luego subimos todos un índice por 1.
Debido a que la ordenación por inserción es una ordenación adaptativa, también la convierte en un ‘algoritmo en línea’, lo que significa que podemos comenzar a ordenar antes de obtener todos los elementos y luego fusionar las listas una vez que se haya completado la ordenación parcial.
Pseudocódigo
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Código
el Siguiente? Ordenar por fusión. Uno de los algoritmos de ordenación más utilizados en los navegadores de hoy en día.
