La clasificación por inserción es un algoritmo de clasificación simple que construye la matriz (o lista) ordenada final , un elemento a la vez, mediante comparaciones . Es mucho menos eficiente en listas grandes que algoritmos más avanzados como el ordenamiento rápido , el ordenamiento en montón o el ordenamiento por combinación . Sin embargo, la ordenación por inserción ofrece varias ventajas:
Cuando las personas clasifican manualmente las cartas en una mano de bridge , la mayoría usa un método similar a la clasificación por inserción. [2]
La ordenación por inserción se itera , consume un elemento de entrada en cada repetición y aumenta una lista de salida ordenada. En cada iteración, la ordenación por inserción elimina un elemento de los datos de entrada, encuentra 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 clasificación generalmente se realiza en el lugar, iterando la matriz y 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 se encuentra al lado de él, en la posición de la matriz anterior marcada). 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 crear un espacio y los inserta en esa posición correcta.
La matriz resultante después de k iteraciones tiene la propiedad de ordenar las primeras k + 1 entradas ("+1" porque se omite la primera entrada). En cada iteración, la primera entrada restante de la entrada se elimina y se inserta en el resultado en la posición correcta, extendiendo así el resultado:
se convierte
con cada elemento mayor que x copiado a la derecha mientras se compara con x .
La variante más común de ordenación por inserción, que opera en matrices, se puede describir de la siguiente manera:
A continuación se muestra el pseudocódigo del algoritmo completo, donde las matrices tienen base cero : [1]
i ← 1 mientras i < longitud(A) j ← yo mientras j > 0 y A[j-1] > A[j] intercambian 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, debido a que el prefijo de un solo elemento A[0:1]está ordenado de manera 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 para que después del bucle, i+1se ordenen los primeros elementos. Tenga en cuenta que el andoperador - en la prueba debe utilizar la evaluación de cortocircuito ; de lo contrario, la prueba podría provocar un error en los límites de la matriz cuando j=0intenta evaluar A[j-1] > A[j](es decir, el acceso A[-1]falla).
Después de expandir la swapoperación in situ como x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(donde xhay una variable temporal), se puede producir una versión un poco 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[yo] j ← yo mientras j > 0 y A[j-1] > x A[j] ← A[j-1] j ← j - 1 terminar mientras A[j] ← x [3] yo ← yo + 1terminar mientras
El nuevo bucle interior desplaza elementos hacia la derecha para dejar espacio para x = A[i].
El algoritmo también se puede implementar de forma recursiva. La recursividad simplemente reemplaza el bucle externo, llamándose a sí mismo y almacenando 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 que comienza con n igual a 1, con n aumenta 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 inserciónSortR(matriz A, int n) si n > 0 inserciónSortR(A, n-1) x ← A[n] j ← norte-1 mientras j >= 0 y A[j] > x A[j+1] ← A[j] j ← j-1 terminar mientras A[j+1] ←x finalizar si finaliza la función
No acorta el código, tampoco 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 recursividad, la pila contiene N referencias a la Amatriz , cada uno con el valor de la variable que lo acompaña 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 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 del peor de los casos consta de todas las matrices donde 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 a la ordenación 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 no sea 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 clasificación rápida utilizan la clasificació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 suele rondar los diez.
Ejemplo: La siguiente tabla muestra los pasos para ordenar la secuencia {3, 7, 4, 9, 5, 2, 6, 1}. En cada paso, se subraya la clave que se está considerando. 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
La ordenación por inserción es muy similar a la ordenación por selección . Como en la ordenación por selección, después de que k pasa por la matriz, los primeros k elementos están ordenados. Sin embargo, la diferencia fundamental entre los dos algoritmos es que la ordenación por inserción escanea hacia atrás desde la clave actual, mientras que la ordenación por selección escanea hacia adelante. Esto da como resultado que la ordenación por selección haga que los primeros k elementos sean los k elementos más pequeños de la entrada sin clasificar, mientras que en la ordenación por inserción son simplemente los primeros k elementos de la entrada.
La principal ventaja de la ordenación por inserción sobre la ordenación por selección es que la ordenación 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 la ordenación por inserción requiere solo una comparación única cuando ( k + 1)-st 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), la ordenación por inserción es claramente más eficiente en comparación con la ordenación por selección. En promedio (asumiendo que el rango del elemento ( k + 1)-st 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. promedio.
En el peor de los casos para la ordenación por inserción (cuando la matriz de entrada está ordenada en orden inverso), 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 elemento ( k + 1)-st en la porción ordenada de la matriz requiere muchos intercambios de elementos para cambiar todos los elementos. de los siguientes elementos, mientras que solo se requiere un intercambio para cada iteración de clasificación de 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 clasificación por selección puede ser preferible en los casos en que escribir en la memoria sea significativamente más costoso que leer, como con EEPROM o memoria flash .
Mientras que algunos algoritmos de divide y vencerás, como la ordenación rápida y la ordenación por combinación , superan a la ordenación por inserción para matrices más grandes, los algoritmos de ordenación no recursivos como la ordenación por inserción o 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 suele estar 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 en un tamaño pequeño. [1]
DL Shell realizó mejoras sustanciales al algoritmo; la versión modificada se llama Shell sort . El algoritmo de clasificación compara elementos separados por una distancia que disminuye en cada pasada. La clasificación de shell ha mejorado claramente los tiempos de ejecución en el trabajo práctico, con dos variantes simples que requieren tiempo de ejecución 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 la interacción humana (como elegir una de un par que se muestra una al lado de la otra), entonces el uso de la ordenación por inserción binaria puede generar mejor interpretación. [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 comparaciones ⌈log 2 n ⌉ 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]
El número de intercambios se puede reducir calculando la posición de varios elementos antes de moverlos. Por ejemplo, si la posición objetivo de dos elementos se calcula antes de moverlos a la posición adecuada, el número de intercambios se puede reducir en aproximadamente un 25% 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 combinació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 combinación . Combina la velocidad de clasificación por inserción en conjuntos de datos pequeños con la velocidad de clasificación por fusión en conjuntos de datos grandes. [8]
Para evitar tener que realizar una serie de intercambios para cada inserción, la entrada podría almacenarse en una lista vinculada , lo que permite unir elementos dentro o fuera de la lista en un tiempo constante cuando se conoce la posición en la lista. Sin embargo, buscar 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 ordenar es O ( n 2 ). Si se utiliza una estructura de datos más sofisticada (por ejemplo, montón o árbol binario ), el tiempo necesario para la búsqueda e inserción se puede reducir significativamente; esta es la esencia de la clasificación en montón y la clasificación en árbol binario .
En 2006, Bender, Martin Farach-Colton y Mosteiro publicaron una nueva variante de clasificación por inserción llamada clasificación de biblioteca o clasificación de inserción con espacios que deja una pequeña cantidad de espacios no utilizados (es decir, "espacios") repartidos por toda la matriz. La ventaja es que las inserciones sólo necesitan cambiar los elementos hasta alcanzar un espacio. Los autores muestran que este algoritmo de clasificación se ejecuta con alta probabilidad en tiempo O ( n log n ). [9]
Si se utiliza una lista de omisión , el tiempo de inserción se reduce a O(log n ) y no se necesitan intercambios porque la lista de omisión se implementa en una estructura de lista vinculada. El tiempo de ejecución final para la inserción sería O ( n log n ).
Si los elementos se almacenan en una lista vinculada, entonces la lista se puede ordenar con O(1) espacio adicional. El algoritmo comienza con una lista inicialmente vacía (y por tanto ordenada de forma trivial). Los elementos de entrada se eliminan de la lista uno por uno y luego se insertan en el lugar adecuado de la lista ordenada. Cuando la lista de entrada está vacía, la lista ordenada tiene el resultado deseado.
estructura LISTA * OrdenarLista1 ( estructura LISTA * pList ) { // cero o un elemento en la lista si ( pList == NULL || pList -> pNext == NULL ) devolver pList ; // encabezado es el primer elemento de la lista ordenada resultante estructura LISTA * cabeza = NULL ; mientras ( pList ! = NULL ) { estructura LISTA * actual = pList ; pList = pList -> pSiguiente ; if ( head == NULL || actual -> iValue < head -> iValue ) { // insertar en el encabezado de la lista ordenada // o como primer elemento en una lista ordenada vacía actual -> pNext = cabeza ; cabeza = actual ; } demás { // inserta 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 -> pSiguiente = p -> pSiguiente ; p -> pSiguiente = actual ; romper ; // hecho } p = p -> pSiguiente ; } } } cabeza de retorno ; }El siguiente algoritmo 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 usar O( n ) espacio de pila.
estructura LISTA { estructura LISTA * pSiguiente ; int iValor ; }; 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 ; /* retira elementos de la lista de entrada uno por uno hasta que quede vacío */ while ( pList != NULL ) { /* recuerda el encabezado */ struct LIST * pHead = pList ; /* puntero final para empalme eficiente */ struct LIST ** ppTrail = & pSorted ; /* sacar la cabeza de la lista */ pList = pList -> pNext ; /* empalmar el encabezado en la lista ordenada en el lugar adecuado */ while ( ! ( * ppTrail == NULL || pHead -> iValue < ( * ppTrail ) -> iValue )) { /* ¿el encabezado pertenece aquí? */ /* no - continúa hacia abajo en la lista */ ppTrail = & ( * ppTrail ) -> pNext ; } pHead -> pNext = * ppTrail ; * ppTrail = pHcabeza ; } volver ordenados ; } 
