¿Alguna vez hay una buena razón para usar Insertion Sort?

Question

Para la clasificación de propósito general, la respuesta parece ser no, como la ordenación rápida, la ordenación de fusión y la clasificación de acumulación tienden a tener un mejor rendimiento en los escenarios de peor y peor promedio. Sin embargo, la ordenación de inserción parece sobresalir en la ordenación incremental, es decir, agregar elementos a una lista de uno en uno durante un período prolongado mientras se mantiene ordenada la lista, especialmente si la clasificación de inserción se implementa como una lista vinculada (O (log) n) caso promedio vs. O (n)). Sin embargo, un montón parece ser capaz de realizar solo (o casi) también para la clasificación incremental (agregar o eliminar un único elemento de un montón tiene el peor escenario de O (log n)). Entonces, ¿qué ofrece exactamente la ordenación por inserción sobre otros algoritmos o montones de clasificación basados ​​en comparación?

Answer 1

De http://www.sorting-algorithms.com/insertion-sort:

Aunque es uno de los algoritmos de clasificación elementales con O (n) tiempo peor de los casos, la inserción tipo es el algoritmo de elección ya sea cuando los datos es casi ordenado (porque es adaptativo) o cuando el tamaño del problema es pequeño (porque tiene una baja sobrecarga de ).

Por estas razones, y debido a que también es estable, la ordenación por inserción es utiliza a menudo como el caso base recursiva (cuando el tamaño del problema es pequeño) para mayores gastos generales de divide y vencerás algoritmos de clasificación, tales como fusionar ordenar o ordenar rápidamente.

Answer 2

La mayoría de los procedimientos de clasificación usarán quicksort y luego sorter de inserción para conjuntos de datos muy pequeños.

Answer 3

Un concepto importante en el análisis de algoritmos es análisis asintótico. En el caso de dos algoritmos con diferentes tiempos de ejecución asintóticos, como uno O (n^2) y un O (nlogn) como es el caso con ordenación de inserción y quicksort respectivamente, no es definitivo que uno sea más rápido que el otro .

La distinción importante con este tipo de análisis es que para suficientemente grande N, un algoritmo será más rápido que otro. Al analizar un algoritmo hasta un término como O (nlogn), se sueltan constantes. Al analizar de forma realista el funcionamiento de un algoritmo, esas constantes serán importantes solo para situaciones de n pequeño.

¿Qué significa esto? Eso significa que para ciertos n pequeños, algunos algoritmos son más rápidos. Este article de EmbeddedGurus.net incluye una perspectiva interesante sobre la elección de diferentes algoritmos de clasificación en el caso de un espacio limitado (16k) y un sistema de memoria limitado. Por supuesto, el artículo hace referencia solo a ordenar una lista de 20 enteros, por lo que las órdenes más grandes de n son irrelevantes. Un código más corto y menos consumo de memoria (además de evitar la recursión) fueron, en última instancia, decisiones más importantes.

El tipo de inserción tiene poca sobrecarga, se puede escribir de manera bastante sucinta y tiene varias ventajas clave: es estable y tiene una carcasa de ejecución bastante rápida cuando la entrada está casi ordenada.

Answer 4

Si hablamos de mantener una lista ordenada, no hay ninguna ventaja sobre algún tipo de árbol, simplemente es más lento.

Bueno, tal vez consume menos memoria o es una implementación más simple.

insertar en una lista ordenada implicará una exploración, lo que significa que cada inserto es O (n), por lo tanto, la clasificación n elementos se convierte en O (n^2)

insertar en un recipiente tal como un árbol de equilibrado, es típicamente log (n), por lo tanto, el género es O (n log (n)) que, por supuesto, es mejor.

Pero para las listas pequeñas, apenas hace ninguna diferencia. Puede usar una ordenación por inserción si tiene que escribirla usted mismo sin ninguna biblioteca, las listas son pequeñas y no le importa el rendimiento.

Answer 5

SÍ,

La ordenación por inserción es mejor que la Ordenación rápida en las listas cortas.

De hecho, una ordenación rápida óptima tiene un umbral de tamaño en el que se detiene y, a continuación, toda la matriz se ordena por inserción por encima de los límites del umbral.

también ...

Para mantener un marcador, binario ordenación por inserción puede ser tan bueno como se pone.

Ver this page.

Answer 6

Sí, hay un motivo para utilizar una ordenación de inserción o una de sus variantes.

Las alternativas de clasificación (clasificación rápida, etc.) de las otras respuestas aquí presuponen que los datos ya están en la memoria y listos para funcionar.

Pero si intenta leer una gran cantidad de datos de una fuente externa más lenta (por ejemplo, un disco duro), se desperdicia una gran cantidad de tiempo ya que el cuello de botella es claramente el canal de datos o la unidad. Simplemente no puede mantenerse al día con la CPU. Una serie natural de esperas ocurre durante cualquier lectura. Estas esperas son desperdiciados ciclos de CPU si no los usa para especie a medida que avanza.

Por ejemplo, si usted fuera a hacer que su solución a este ser los siguientes:

1. leer un montón de datos en un bucle dedicado a la memoria
2. Ordenar que los datos

Usted muy probablemente tomaría más tiempo que si hicieras lo siguiente en dos hilos.

Tema A:

1. Leer un dato
2. lugar de referencia en la cola FIFO
3. (Repetir hasta que los datos agotados por unidad)

Tema B:

1. Obtener un dato de la cola FIFO
2. insertarlo en el lugar adecuado en su lista ordenada
3. (repetir hasta cola vacía y el hilo A dice "hecho").

... lo anterior le permitirá utilizar el tiempo perdido de otra manera. Nota: El hilo B no impide el progreso del hilo A.

Cuando los datos se hayan leído por completo, se habrán clasificado y estarán listos para su uso.

Answer 7

Un concepto importante en el análisis de algoritmos es el análisis asintótico. En el caso de dos algoritmos con diferentes tiempos de ejecución asintóticos, como uno O (n^2) y un O (nlogn) como es el caso con el ordenamiento de inserción y el ordenamiento rápido respectivamente, no está claro si uno es más rápido que el otro.

La distinción importante con este tipo de análisis es que para un N suficientemente grande, un algoritmo será más rápido que otro. Al analizar un algoritmo hasta un término como O (nlogn), se sueltan constantes. Al analizar de forma realista el funcionamiento de un algoritmo, esas constantes serán importantes solo para situaciones de n pequeño.

¿Qué significa esto? Eso significa que para ciertos n pequeños, algunos algoritmos son más rápidos. Este artículo de EmbeddedGurus.net incluye una perspectiva interesante sobre la elección de diferentes algoritmos de clasificación en el caso de un espacio limitado (16k) y un sistema de memoria limitado. Por supuesto, el artículo hace referencia solo a ordenar una lista de 20 enteros, por lo que las órdenes más grandes de n son irrelevantes. Un código más corto y menos consumo de memoria (además de evitar la recursión) fueron, en última instancia, decisiones más importantes.

El tipo de inserción tiene poca sobrecarga, se puede escribir de manera bastante sucinta y tiene varias ventajas clave: es estable y tiene una carcasa de ejecución bastante rápida cuando la entrada está casi ordenada.

Answer 8

Para matrices pequeñas, la ordenación de inserción se realiza más rápido que el quicksort. Java 7 y Java 8 usan el enlace dinámico de doble pivote para ordenar tipos de datos primitivos. Dual pivot quicksort realiza un quicksort típico de un solo pivote. De acuerdo con el algoritmo de quicksort doble pivote:

1. Para pequeñas arrays (longitud < 27), utilizar el algoritmo de inserción tipo.
2. Elija dos de pivote ...........

Definitivamente ordenación por inserción fuera realiza la clasificación rápida para las pequeñas matrices y es por eso que está interruptor de ordenación por inserción para las matrices de longitud inferior a 27. La razón podría ser que no hay recurrencias en la ordenación por inserción.

Fuente: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf