algorithm - bubble - merge sort

¿Hay alguna vez una buena razón para usar Insertion Sort? (7)

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

Aunque es uno de los algoritmos de clasificación elementales con O (n ² ) del peor de los casos, la ordenación por inserción es el algoritmo de elección cuando los datos están casi ordenados (porque es adaptativo) o cuando el tamaño del problema es pequeño (porque tiene poca sobrecarga).
Por estas razones, y porque también es estable, el ordenamiento de inserción se usa a menudo como el caso base recursivo (cuando el tamaño del problema es pequeño) para algoritmos de clasificación de división y conquista superiores, tales como tipo de fusión o clasificación rápida.

Para la clasificación de propósito general, la respuesta parece ser no, como la ordenación rápida, la ordenación por fusión y la clasificación por 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?

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.

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

Para matrices pequeñas (longitud <27), use el algoritmo de ordenación de Inserción.
Elija dos pivotes ...........

Definitivamente, la ordenación de inserción realiza el envío rápido para matrices pequeñas y es por eso que se cambia a ordenar por inserción para matrices de una 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

SÍ,

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

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

También...

Para mantener un marcador, la Clasificación de inserción binaria puede ser tan buena como sea posible.

Vea esta página .

Sí, hay una razón para usar un tipo de inserción o una de sus variantes.

Las alternativas de clasificación (clasificación rápida, etc.) de las otras respuestas aquí suponen 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 propia unidad. Simplemente no puede mantenerse al día con la CPU. Una serie natural de esperas ocurre durante cualquier lectura. Estas esperas son ciclos de CPU desperdiciados a menos que los uses para ordenar sobre la marcha .

Por ejemplo, si tuviera que hacer que su solución a esto fuera la siguiente:

Leer una tonelada de datos en un bucle dedicado en la memoria
Clasifica esos datos

Probablemente tomarías más tiempo que si hicieras lo siguiente en dos hilos.

Tema A:

Leer un dato
Colocar dato en cola FIFO
(Repita hasta que se agoten los datos del disco)

Hilo B:

Obtener un dato de la cola FIFO
Insértelo en el lugar correcto en su lista ordenada
(repita hasta que la cola esté vacía Y el hilo A dice "hecho").

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

Para cuando los datos estén completamente leídos, se habrán ordenado y estarán listos para su uso.

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

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

Insertar en una lista ordenada implicará un escaneo, lo que significa que cada inserción es O (n), por lo que la clasificación de n elementos se convierte en O (n ^ 2)

Insertar en un contenedor como un árbol balanceado, es típicamente log (n), por lo tanto, el tipo es O (n log (n)) que es, por supuesto, mejor.

Pero para 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.

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.

Entonces, ¿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 varios beneficios clave: es estable y tiene un caso de ejecución bastante rápido cuando la entrada está casi ordenada.