El ordenamiento por inserción es un algoritmo de ordenamiento simple que construye la matriz (o lista) ordenada final elemento por elemento mediante comparaciones . Es mucho menos eficiente en listas grandes que algoritmos más avanzados como quicksort , heapsort o merge sort . Sin embargo, el ordenamiento por inserción ofrece varias ventajas:
Cuando las personas clasifican manualmente las cartas en una mano de bridge , la mayoría utiliza un método similar a la clasificación por inserción. [2]
La ordenación por inserción itera , consume un elemento de entrada en cada repetición y genera una lista de salida ordenada. En cada iteración, la ordenación por inserción elimina un elemento de los datos de entrada, busca la ubicación a la que pertenece dentro de la lista ordenada y lo inserta allí. Se repite hasta que no queden elementos de entrada.
La ordenación se realiza normalmente en el lugar, iterando hacia arriba en la matriz, haciendo crecer la lista ordenada detrás de ella. En cada posición de la matriz, compara el valor allí con el valor más grande en la lista ordenada (que resulta estar junto a él, en la posición de matriz anterior que se verificó). Si es más grande, deja el elemento en su lugar y pasa al siguiente. Si es más pequeño, encuentra la posición correcta dentro de la lista ordenada, desplaza todos los valores más grandes hacia arriba para hacer un espacio y los inserta en esa posición correcta.
La matriz resultante después de k iteraciones tiene la propiedad de que las primeras k + 1 entradas están ordenadas ("+1" porque se omite la primera entrada). En cada iteración, se elimina la primera entrada restante de la entrada y se inserta en el resultado en la posición correcta, extendiendo así el resultado:
se convierte en
con cada elemento mayor que x copiado a la derecha a medida que se compara con x .
La variante más común del ordenamiento por inserción, que opera sobre matrices, se puede describir de la siguiente manera:
A continuación se muestra el pseudocódigo del algoritmo completo, donde las matrices están basadas en cero : [1]
i ← 1 mientras i < longitud(A) j ← yo mientras j > 0 y A[j-1] > A[j] intercambiamos A[j] y A[j-1] j ← j-1 terminar mientras yo ← yo + 1terminar mientras
El bucle externo recorre todos los elementos excepto el primero, porque el prefijo de un solo elemento A[0:1]está ordenado de forma trivial, por lo que la invariante de que las primeras ientradas están ordenadas es verdadera desde el principio. El bucle interno mueve el elemento A[i]a su lugar correcto de modo que después del bucle, los primeros i+1elementos están ordenados. Tenga en cuenta que el andoperador - en la prueba debe utilizar la evaluación de cortocircuito , de lo contrario, la prueba puede dar como resultado un error de límites de matriz , cuando j=0y intenta evaluar A[j-1] > A[j](es decir, el acceso A[-1]falla).
Después de expandir la swapoperación en el lugar como x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(donde xes una variable temporal), se puede producir una versión ligeramente más rápida que se mueve A[i]a su posición de una sola vez y solo realiza una asignación en el cuerpo del bucle interno: [1]
i ← 1 mientras i < longitud(A) x ← A[i] j ← yo mientras j > 0 y A[j-1] > x A[j] ← A[j-1] j ← j-1 fin mientras A[j] ← x [3] yo ← yo + 1terminar mientras
El nuevo bucle interno desplaza los elementos hacia la derecha para liberar un espacio para x = A[i].
El algoritmo también se puede implementar de forma recursiva. La recursión simplemente reemplaza el bucle externo, se llama a sí misma y almacena valores sucesivamente más pequeños de n en la pila hasta que n sea igual a 0, donde la función luego regresa a la cadena de llamadas para ejecutar el código después de cada llamada recursiva comenzando con n igual a 1, con n aumentando en 1 a medida que cada instancia de la función regresa a la instancia anterior. La llamada inicial sería insertionSortR(A, length(A)-1) .
función insertionSortR(matriz A, int n) si n > 0 ordenamientoporinserciónR(A, n-1) x ← Un[n] j ← n-1 mientras j >= 0 y A[j] > x A[j+1] ← A[j] j ← j-1 terminar mientras A[j+1] ← x fin si fin de función
Esto no hace que el código sea más corto ni reduce el tiempo de ejecución, pero aumenta el consumo de memoria adicional de O(1) a O(N) (en el nivel más profundo de recursión, la pila contiene N referencias a la Amatriz, cada una con el valor correspondiente de la variable ndesde N hasta 1).
La entrada en el mejor de los casos es una matriz que ya está ordenada. En este caso, la ordenación por inserción tiene un tiempo de ejecución lineal (es decir, O( n )). Durante cada iteración, el primer elemento restante de la entrada solo se compara con el elemento que se encuentra más a la derecha de la subsección ordenada de la matriz.
La entrada más simple en el peor de los casos es una matriz ordenada en orden inverso. El conjunto de todas las entradas en el peor de los casos consta de todas las matrices en las que cada elemento es el más pequeño o el segundo más pequeño de los elementos anteriores. En estos casos, cada iteración del bucle interno escaneará y desplazará toda la subsección ordenada de la matriz antes de insertar el siguiente elemento. Esto le da al ordenamiento por inserción un tiempo de ejecución cuadrático (es decir, O( n 2 )).
El caso promedio también es cuadrático, [4] lo que hace que la ordenación por inserción sea poco práctica para ordenar matrices grandes. Sin embargo, la ordenación por inserción es uno de los algoritmos más rápidos para ordenar matrices muy pequeñas, incluso más rápido que la ordenación rápida ; de hecho, las buenas implementaciones de ordenación rápida utilizan la ordenación por inserción para matrices más pequeñas que un cierto umbral, también cuando surgen como subproblemas; el umbral exacto debe determinarse experimentalmente y depende de la máquina, pero comúnmente está alrededor de diez.
Ejemplo: La siguiente tabla muestra los pasos para ordenar la secuencia {3, 7, 4, 9, 5, 2, 6, 1}. En cada paso, la clave en cuestión está subrayada. La clave que se movió (o se dejó en su lugar porque era la más grande considerada hasta ahora) en el paso anterior está marcada con un asterisco.
3 7 4 9 5 2 6 13* 7 4 9 5 2 6 13 7* 4 9 5 2 6 13 4* 7 9 5 2 6 13 4 7 9* 5 2 6 13 4 5* 7 9 2 6 12* 3 4 5 7 9 6 12 3 4 5 6* 7 9 11* 2 3 4 5 6 7 9
El ordenamiento por inserción es muy similar al ordenamiento por selección . Al igual que en el ordenamiento por selección, después de que k elementos pasen por la matriz, los primeros k elementos están en orden ordenado. Sin embargo, la diferencia fundamental entre los dos algoritmos es que el ordenamiento por inserción escanea hacia atrás a partir de la clave actual, mientras que el ordenamiento por selección escanea hacia adelante. Esto da como resultado que el ordenamiento por selección haga que los primeros k elementos sean los k elementos más pequeños de la entrada sin ordenar, mientras que en el ordenamiento por inserción son simplemente los primeros k elementos de la entrada.
La principal ventaja del ordenamiento por inserción sobre el ordenamiento por selección es que el ordenamiento por selección siempre debe escanear todos los elementos restantes para encontrar el elemento más pequeño absoluto en la parte no ordenada de la lista, mientras que el ordenamiento por inserción requiere solo una única comparación cuando el ( k + 1) -ésimo elemento es mayor que el k -ésimo elemento; cuando esto es cierto con frecuencia (por ejemplo, si la matriz de entrada ya está ordenada o parcialmente ordenada), el ordenamiento por inserción es claramente más eficiente en comparación con el ordenamiento por selección. En promedio (asumiendo que el rango del ( k + 1) -ésimo elemento es aleatorio), el ordenamiento por inserción requerirá comparar y desplazar la mitad de los k elementos anteriores, lo que significa que el ordenamiento por inserción realizará aproximadamente la mitad de comparaciones que el ordenamiento por selección en promedio.
En el peor de los casos para la ordenación por inserción (cuando la matriz de entrada está ordenada de forma inversa), la ordenación por inserción realiza tantas comparaciones como la ordenación por selección. Sin embargo, una desventaja de la ordenación por inserción sobre la ordenación por selección es que requiere más escrituras debido al hecho de que, en cada iteración, insertar el ( k + 1) -er elemento en la parte ordenada de la matriz requiere muchos intercambios de elementos para desplazar todos los elementos siguientes, mientras que solo se requiere un único intercambio para cada iteración de la ordenación por selección. En general, la ordenación por inserción escribirá en la matriz O( n 2 ) veces, mientras que la ordenación por selección escribirá solo O( n ) veces. Por esta razón, la ordenación por selección puede ser preferible en casos en los que escribir en la memoria es significativamente más costoso que leer, como con EEPROM o memoria flash .
Si bien algunos algoritmos de división y conquista, como quicksort y mergesort, superan al ordenamiento por inserción para matrices más grandes, los algoritmos de ordenamiento no recursivos, como el ordenamiento por inserción o el ordenamiento por selección, son generalmente más rápidos para matrices muy pequeñas (el tamaño exacto varía según el entorno y la implementación, pero normalmente es de entre 7 y 50 elementos). Por lo tanto, una optimización útil en la implementación de esos algoritmos es un enfoque híbrido, utilizando el algoritmo más simple cuando la matriz se ha dividido a un tamaño pequeño. [1]
DL Shell realizó mejoras sustanciales al algoritmo; la versión modificada se llama Shell sort . El algoritmo de ordenamiento compara elementos separados por una distancia que disminuye en cada pasada. Shell sort ha mejorado notablemente los tiempos de ejecución en el trabajo práctico, con dos variantes simples que requieren un tiempo de ejecución de O( n 3/2 ) y O( n 4/3 ). [5] [6]
Si el costo de las comparaciones excede el costo de los intercambios, como es el caso, por ejemplo, con las claves de cadena almacenadas por referencia o con interacción humana (como elegir una de un par que se muestra lado a lado), entonces el uso de la ordenación por inserción binaria puede producir un mejor rendimiento. [7] La ordenación por inserción binaria emplea una búsqueda binaria para determinar la ubicación correcta para insertar nuevos elementos y, por lo tanto, realiza ⌈log 2 n ⌉ comparaciones en el peor de los casos. Cuando se busca e inserta cada elemento de la matriz, esto es O( n log n ) . [7] El algoritmo en su conjunto todavía tiene un tiempo de ejecución de O( n 2 ) en promedio debido a la serie de intercambios necesarios para cada inserción. [7]
La cantidad de intercambios se puede reducir calculando la posición de varios elementos antes de moverlos. Por ejemplo, si se calcula la posición de destino de dos elementos antes de moverlos a la posición adecuada, la cantidad de intercambios se puede reducir en un 25 % aproximadamente para datos aleatorios. En el caso extremo, esta variante funciona de manera similar a la ordenación por combinación .
Una variante denominada ordenación por fusión binaria utiliza una ordenación por inserción binaria para ordenar grupos de 32 elementos, seguida de una ordenación final mediante ordenación por fusión . Combina la velocidad de la ordenación por inserción en conjuntos de datos pequeños con la velocidad de la ordenación por fusión en conjuntos de datos grandes. [8]
Para evitar tener que hacer una serie de intercambios para cada inserción, la entrada podría almacenarse en una lista enlazada , que permite que los elementos se empalmen dentro o fuera de la lista en tiempo constante cuando se conoce la posición en la lista. Sin embargo, la búsqueda en una lista enlazada requiere seguir secuencialmente los enlaces hasta la posición deseada: una lista enlazada no tiene acceso aleatorio, por lo que no puede utilizar un método más rápido como la búsqueda binaria. Por lo tanto, el tiempo de ejecución requerido para la búsqueda es O( n ) , y el tiempo para la ordenación es O( n2 ). Si se utiliza una estructura de datos más sofisticada (por ejemplo, montón o árbol binario ), el tiempo requerido para la búsqueda y la inserción se puede reducir significativamente; esta es la esencia de la ordenación por montón y la ordenación por árbol binario .
En 2006, Bender, Martin Farach-Colton y Mosteiro publicaron una nueva variante de ordenamiento por inserción denominada ordenamiento por biblioteca o ordenamiento por inserción con espacios , que deja una pequeña cantidad de espacios sin usar (es decir, "espacios vacíos") distribuidos por toda la matriz. La ventaja es que las inserciones solo necesitan desplazar elementos hasta que se alcance un espacio vacío. Los autores demuestran que este algoritmo de ordenamiento se ejecuta con alta probabilidad en tiempo O( n log n ) . [9]
Si se utiliza una lista de saltos , el tiempo de inserción se reduce a O(log n ) y no se necesitan intercambios porque la lista de saltos se implementa en una estructura de lista enlazada. El tiempo de ejecución final para la inserción sería O( n log n ) .
Si los elementos se almacenan en una lista enlazada, la lista se puede ordenar con O(1) espacio adicional. El algoritmo comienza con una lista inicialmente vacía (y por lo tanto trivialmente ordenada). Los elementos de entrada se extraen de la lista uno a la vez y luego se insertan en el lugar apropiado en la lista ordenada. Cuando la lista de entrada está vacía, la lista ordenada tiene el resultado deseado.
estructura LISTA * SortList1 ( estructura LISTA * pList ) { // cero o un elemento en la lista si ( pList == NULL || pList -> pNext == NULL ) devolver pList ; // head es el primer elemento de la lista ordenada resultante estructura LISTA * cabeza = NULL ; mientras ( pList != NULL ) { estructura LIST * actual = pList ; pList = pList -> pNext ; si ( cabeza == NULL || actual -> iValor < cabeza -> iValor ) { // insertar en el encabezado de la lista ordenada // o como el primer elemento en una lista ordenada vacía actual -> pNext = cabeza ; cabeza = actual ; } demás { // Insertar el elemento actual en la posición adecuada en una lista ordenada no vacía estructura LISTA * p = cabeza ; mientras ( p != NULL ) { if ( p -> pNext == NULL || // último elemento de la lista ordenada actual -> iValue < p -> pNext -> iValue ) // mitad de la lista { // insertar en el medio de la lista ordenada o como último elemento actual -> pNext = p -> pNext ; p -> pNext = actual ; descanso ; // hecho } p = p -> pSiguiente ; } } } retorno de cabeza ; }El algoritmo que se muestra a continuación utiliza un puntero final [10] para la inserción en la lista ordenada. Un método recursivo más simple reconstruye la lista cada vez (en lugar de empalmar) y puede utilizar un espacio de pila O( n ).
estructura LISTA { estructura LISTA * pNext ; int iValue ; }; struct LIST * SortList ( struct LIST * pList ) { // cero o un elemento en la lista if ( ! pList || ! pList -> pNext ) return pList ; /* construye la matriz ordenada a partir de la lista vacía */ struct LIST * pSorted = NULL ; /* tomar elementos de la lista de entrada uno por uno hasta que esté vacía */ while ( pList != NULL ) { /* recordar la cabecera */ struct LIST * pHead = pList ; /* puntero final para empalme eficiente */ struct LIST ** ppTrail = & pSorted ; /* sacar la cabecera de la lista */ pList = pList -> pNext ; /* empalmar la cabeza en la lista ordenada en el lugar apropiado */ while ( ! ( * ppTrail == NULL || pHead -> iValue < ( * ppTrail ) -> iValue )) { /* ¿cabeza pertenece aquí? */ /* no - continuar hacia abajo en la lista */ ppTrail = & ( * ppTrail ) -> pNext ; } pHead -> pNext = * ppTrail ; * ppTrail = pHcabeza ; } devuelve pSorted ; } 
