eso es un excelente enlace por cierto, felicitaciones y un 1
ninesided
55
El tipo de burbuja es terrible. Siempre es O (n ^ 2). Al menos, retíralo de tu respuesta para que sea correcto, por favor.
jjnguy
79
jjnguy, eso es simplemente incorrecto. Creo que necesitas volver a tomar tu clase de algoritmos. En datos casi ordenados (es un caso adaptativo) es O (N). Sin embargo, toma 2 pasadas a través de los datos y la inserción solo toma 1 para datos casi ordenados, lo que hace que la inserción sea la ganadora. Sin embargo
mmcdole
3
Sin embargo, el rendimiento se degrada muy mal si sus datos nunca se ordenan. Todavía no lo usaría, personalmente.
Ese es exactamente el tipo de respuesta que he estado buscando, leí libros, pero no encuentro ninguna explicación clara para la selección de alogoritmos en casos particulares, ¿podría elaborar esto o pasar un enlace para que pueda profundizar en es un poco mas? Gracias
Simran kaur
9
Debe agregar "Los datos ya están ordenados por otro criterio => MERGE SORT"
Jim Hunziker
30
timsort
Timsort es "un mergesort natural adaptable, estable" con " rendimiento sobrenatural en muchos tipos de matrices parcialmente ordenadas (se necesitan menos de 1g (N!) Comparaciones y tan pocas como N-1)". Python incorporadosort()ha usado este algoritmo por algún tiempo, aparentemente con buenos resultados. Está específicamente diseñado para detectar y aprovechar subsecuencias parcialmente ordenadas en la entrada, que a menudo ocurren en conjuntos de datos reales. A menudo es el caso en el mundo real que las comparaciones son mucho más caras que intercambiar elementos en una lista, ya que uno simplemente intercambia punteros, lo que a menudo hace que timsort sea una excelente opción. Sin embargo, si sabe que sus comparaciones siempre son muy baratas (por ejemplo, escribir un programa de juguete para clasificar enteros de 32 bits), existen otros algoritmos que probablemente tengan un mejor rendimiento. La forma más fácil de aprovechar timsort es, por supuesto, usar Python, pero dado que Python es de código abierto, también puede pedir prestado el código. Alternativamente, la descripción anterior contiene detalles más que suficientes para escribir su propia implementación.
@JF Sebastian: ¡timsort es mucho más rápido que las lg(n!)comparaciones en una matriz casi ordenada, hasta el final O(n)! El | @behrooz: Ningún tipo de comparación puede tener un caso promedio mejor que O(n log n), y lg(n!)es O(n log n). Entonces, el peor caso de Timsort es asintóticamente no peor que el de cualquier otro tipo de comparación. Además, su mejor caso es mejor o igual que cualquier otro tipo de comparación.
Artelius
3
Timsort sigue siendo O (nlogn) en el peor de los casos, pero sus buenos casos son bastante agradables. Aquí hay una comparación, con algunos gráficos: stromberg.dnsalias.org/~strombrg/sort-comparison Tenga en cuenta que timsort en Cython no fue tan rápido como el construido en Python en C.
user1277476
19
Tipo de inserción con el siguiente comportamiento:
Para cada elemento ken las ranuras 1..n, primero verifique si el[k] >= el[k-1]. Si es así, vaya al siguiente elemento. (Obviamente, omita el primer elemento).
De lo contrario, utilice la búsqueda binaria en elementos 1..k-1para determinar la ubicación de inserción, luego pase los elementos. (Es posible hacer esto sólo si k>Ten Tun cierto valor umbral, con un pequeño kesto es una exageración.)
Este método hace el menor número de comparaciones.
Creo que el ordenamiento de burbujas podría superar esto si el número de elementos sin clasificar es muy pequeño (como uno o dos), pero en general esto me parece probablemente la mejor solución.
Sol
Debido al paso 1, para cualquier elemento que ya esté ordenado, hay exactamente una comparación y cero movimientos de datos, que obviamente es lo mejor que puede hacer. El paso 2 es el que podría mejorar, pero la burbuja moverá la misma cantidad de elementos y podría tener más comparaciones, dependiendo de su impl.
Jason Cohen
En realidad, pensándolo mejor, creo que el tipo de burbuja es más fuerte de lo que pensaba. En realidad es una pregunta bastante complicada. Por ejemplo, si toma el caso donde la lista está completamente ordenada, excepto que el elemento que debería ser el último es el primero, la clasificación de burbujas superará ampliamente lo que usted describe.
Sol
Traté de implementar esto, pero la búsqueda binaria no es una gran mejora, ya que todavía tiene que mover todo el bloque para insertar el elemento. Entonces, en lugar de 2xrange, obtienes range + logb (range).
Se basa en la clasificación rápida, pero evita el peor comportamiento que tiene la clasificación rápida para listas casi ordenadas.
El truco es que este algoritmo de clasificación detecta los casos en los que el ordenamiento rápido entra en el peor de los casos y cambia a ordenar o combinar. Las particiones casi ordenadas se detectan mediante algún método de partición no ingenuo y las particiones pequeñas se manejan usando la ordenación por inserción.
Obtiene el mejor de todos los algoritmos de clasificación principales por el costo de un código más complejo. Y puede estar seguro de que nunca se encontrará con el peor comportamiento, sin importar cómo se vean sus datos.
Si es un programador de C ++, verifique su algoritmo std :: sort. Es posible que ya use una ordenación introspectiva internamente.
Splaysort es un oscuro método de clasificación basado en splay trees , un tipo de árbol binario adaptativo. Splaysort es bueno no solo para datos parcialmente ordenados, sino también para datos parcialmente ordenados en reversa, o de hecho, cualquier dato que tenga algún tipo de orden preexistente. Es O (nlogn) en el caso general y O (n) en el caso en que los datos se ordenan de alguna manera (hacia adelante, hacia atrás, organo-pipe, etc.).
Su gran ventaja sobre la ordenación por inserción es que no vuelve al comportamiento O (n ^ 2) cuando los datos no están ordenados en absoluto, por lo que no necesita estar absolutamente seguro de que los datos están ordenados parcialmente antes de usarlos .
Su desventaja es la sobrecarga de espacio adicional de la estructura del árbol de extensión que necesita, así como el tiempo requerido para construir y destruir el árbol de extensión. Pero dependiendo del tamaño de los datos y la cantidad de clasificación previa que espera, la sobrecarga puede valer la pena por el aumento de la velocidad.
El smoothsort de Dijkstra es un gran tipo de datos ya ordenados. Es una variante de montón que se ejecuta en O (n lg n) en el peor de los casos y O (n) en el mejor de los casos. Yo escribí un análisis del algoritmo, en caso de que usted es curioso cómo funciona.
La combinación natural es otra muy buena para esto: es una variante de combinación ascendente que funciona tratando la entrada como la concatenación de múltiples rangos ordenados diferentes, luego usando el algoritmo de combinación para unirlos. Repite este proceso hasta que se ordene todo el rango de entrada. Esto se ejecuta en tiempo O (n) si los datos ya están ordenados y O (n lg n) en el peor de los casos. Es muy elegante, aunque en la práctica no es tan bueno como otros tipos adaptativos como Timsort o smoothsort.
¿Cuáles son las constantes de tiempo de ejecución de smoothsort en comparación con otros algoritmos de clasificación? (es decir, tiempo de ejecución (smoothsort) / tiempo de ejecución (insertionsort) para los mismos datos)
Arne Babenhauserheide
4
Si los elementos ya están ordenados o solo hay pocos elementos, ¡sería un caso de uso perfecto para la inserción de clasificación!
La ordenación por inserción lleva tiempo O (n + el número de inversiones).
Una inversión es un par (i, j)tal que i < j && a[i] > a[j]. Es decir, un par fuera de servicio.
Una medida de estar "casi ordenado" es el número de inversiones: se podría tomar "datos casi ordenados" como datos con pocas inversiones. Si se sabe que el número de inversiones es lineal (por ejemplo, acaba de agregar elementos O (1) a una lista ordenada), la ordenación por inserción toma tiempo O (n).
Como todos los demás dijeron, tenga cuidado con Quicksort ingenuo, que puede tener un rendimiento O (N ^ 2) en datos ordenados o casi ordenados. Sin embargo, con un algoritmo apropiado para la elección del pivote (ya sea aleatorio o mediana de tres, consulte Elección de un pivote para Quicksort ), Quicksort seguirá funcionando de manera sensata.
En general, la dificultad para elegir algoritmos como la ordenación por inserción radica en decidir cuándo los datos están lo suficientemente desordenados como para que Quicksort sea realmente más rápido.
No voy a pretender tener todas las respuestas aquí, porque creo que obtener las respuestas reales puede requerir codificar los algoritmos y perfilarlos con muestras de datos representativos. Pero he estado pensando en esta pregunta toda la noche, y esto es lo que se me ha ocurrido hasta ahora, y algunas conjeturas sobre qué funciona mejor y dónde.
Sea N el número total de artículos, M sea el número fuera de servicio.
El ordenamiento de burbujas tendrá que hacer que algo como 2 * M + 1 pase por todos los N elementos. Si M es muy pequeño (0, 1, 2?), Creo que será muy difícil de superar.
Si M es pequeño (digamos menos que log N), la ordenación por inserción tendrá un gran rendimiento promedio. Sin embargo, a menos que haya un truco que no esté viendo, tendrá un rendimiento muy malo en el peor de los casos. (¿Correcto? Si el último elemento del pedido es el primero, debe insertar cada elemento, por lo que puedo ver, lo que matará el rendimiento). Supongo que hay un algoritmo de clasificación más confiable para esto. caso, pero no sé de qué se trata.
Si M es más grande (digamos igual o mayor que log N), la clasificación introspectiva es casi seguramente la mejor.
Excepción a todo eso: si realmente sabe de antemano qué elementos no están clasificados, entonces su mejor opción será extraer esos elementos, ordenarlos usando una clasificación introspectiva y fusionar las dos listas ordenadas en una sola lista ordenada. Si pudiera averiguar rápidamente qué elementos están fuera de servicio, esta también sería una buena solución general, pero no he podido encontrar una manera simple de hacerlo.
Reflexiones adicionales (de la noche a la mañana): si M + 1 <N / M, puede escanear la lista buscando una serie de N / M en una fila ordenada y luego expandir esa serie en cualquier dirección para encontrar la salida -encargar artículos. Eso tomará como máximo 2N comparaciones. A continuación, puede ordenar los elementos sin clasificar y hacer una fusión ordenada en las dos listas. Las comparaciones totales deberían ser inferiores a algo como 4N + M log2 (M), que va a superar cualquier rutina de clasificación no especializada, creo. (Aún más pensado: esto es más complicado de lo que estaba pensando, pero todavía creo que es razonablemente posible).
Otra interpretación de la pregunta es que puede haber muchos artículos fuera de servicio, pero están muy cerca de donde deberían estar en la lista. (Imagínese comenzar con una lista ordenada e intercambiar cualquier otro elemento con el que viene después). En ese caso, creo que la clasificación de burbujas funciona muy bien: creo que el número de pases será proporcional al más alejado fuera de lugar de un elemento es. La ordenación por inserción funcionará mal, porque cada elemento fuera de servicio activará una inserción. Sospecho que el tipo introspectivo o algo así también funcionará bien.
Si necesita una implementación específica para ordenar algoritmos, estructuras de datos o cualquier cosa que tenga un enlace a lo anterior, ¿podría recomendarle el excelente proyecto "Estructuras de datos y algoritmos" en CodePlex?
Tendrá todo lo que necesita sin reinventar la rueda.
Esta buena colección de algoritmos de clasificación para este propósito en las respuestas parece carecer de Gnome Sort , que también sería adecuada, y probablemente requiera el menor esfuerzo de implementación.
La ordenación por inserción es el mejor caso O (n) en la entrada ordenada. Y está muy cerca de la entrada clasificada en su mayoría (mejor que la clasificación rápida).
La consistencia no es motivo de preocupación aquí. Heapsort dará O (n lg n) incluso en datos ordenados, y no es realmente adaptativo. Las opciones viables pueden ser: Ordenación por inserción, Timsort y Bubblesort.
Max
0
El ordenamiento de burbujas (o, más seguro aún, el ordenamiento de burbujas bidireccional) es probablemente ideal para listas clasificadas en su mayoría, aunque apuesto a que un ordenamiento de peine ajustado (con un tamaño de separación inicial mucho más bajo) sería un poco más rápido cuando la lista no No tan perfectamente ordenado. La clasificación de peine se degrada a clasificación de burbujas.
Esta prueba de eficiencia del algoritmo "en lo que a mí concierne" me iluminó el día :) Sin embargo, en serio, al escribir "eliminar e insertar", ¿te refieres a Insertion Sort (que ya se mencionó en respuestas anteriores), u ofreces ¿Un nuevo tipo de algoritmo? Si es así, expanda su respuesta.
yoniLavi
0
El tipo de burbuja es definitivamente el ganador. El siguiente en el radar sería el de inserción.
Te sugiero que eches un vistazo a las respuestas disponibles antes de publicar para evitar duplicados.
angainor
-1
Manténgase alejado de QuickSort, es muy ineficiente para los datos previamente ordenados. La ordenación por inserción maneja bien los datos casi ordenados moviendo la menor cantidad de valores posible.
Respuestas:
Basado en el método altamente científico de ver gifs animados , diría que los tipos de inserción y burbuja son buenos candidatos.
fuente
Solo unos pocos elementos => ORDEN DE INSERCIÓN
La mayoría de los artículos ya están ordenados => ORDEN DE INSERCIÓN
Preocupado por los peores escenarios => HEAP SORT
Interesado en un buen resultado de caso promedio => QUICKSORT
Los elementos se extraen de un universo denso => ORDEN DE CUBO
Deseo de escribir el menor código posible => ORDEN DE INSERCIÓN
fuente
timsort
Timsort es "un mergesort natural adaptable, estable" con " rendimiento sobrenatural en muchos tipos de matrices parcialmente ordenadas (se necesitan menos de 1g (N!) Comparaciones y tan pocas como N-1)". Python incorporado
sort()ha usado este algoritmo por algún tiempo, aparentemente con buenos resultados. Está específicamente diseñado para detectar y aprovechar subsecuencias parcialmente ordenadas en la entrada, que a menudo ocurren en conjuntos de datos reales. A menudo es el caso en el mundo real que las comparaciones son mucho más caras que intercambiar elementos en una lista, ya que uno simplemente intercambia punteros, lo que a menudo hace que timsort sea una excelente opción. Sin embargo, si sabe que sus comparaciones siempre son muy baratas (por ejemplo, escribir un programa de juguete para clasificar enteros de 32 bits), existen otros algoritmos que probablemente tengan un mejor rendimiento. La forma más fácil de aprovechar timsort es, por supuesto, usar Python, pero dado que Python es de código abierto, también puede pedir prestado el código. Alternativamente, la descripción anterior contiene detalles más que suficientes para escribir su propia implementación.fuente
lg(n!)comparaciones en una matriz casi ordenada, hasta el finalO(n)! El | @behrooz: Ningún tipo de comparación puede tener un caso promedio mejor queO(n log n), ylg(n!)esO(n log n). Entonces, el peor caso de Timsort es asintóticamente no peor que el de cualquier otro tipo de comparación. Además, su mejor caso es mejor o igual que cualquier otro tipo de comparación.Tipo de inserción con el siguiente comportamiento:
ken las ranuras1..n, primero verifique siel[k] >= el[k-1]. Si es así, vaya al siguiente elemento. (Obviamente, omita el primer elemento).1..k-1para determinar la ubicación de inserción, luego pase los elementos. (Es posible hacer esto sólo sik>TenTun cierto valor umbral, con un pequeñokesto es una exageración.)Este método hace el menor número de comparaciones.
fuente
Prueba el tipo introspectivo. http://en.wikipedia.org/wiki/Introsort
Se basa en la clasificación rápida, pero evita el peor comportamiento que tiene la clasificación rápida para listas casi ordenadas.
El truco es que este algoritmo de clasificación detecta los casos en los que el ordenamiento rápido entra en el peor de los casos y cambia a ordenar o combinar. Las particiones casi ordenadas se detectan mediante algún método de partición no ingenuo y las particiones pequeñas se manejan usando la ordenación por inserción.
Obtiene el mejor de todos los algoritmos de clasificación principales por el costo de un código más complejo. Y puede estar seguro de que nunca se encontrará con el peor comportamiento, sin importar cómo se vean sus datos.
Si es un programador de C ++, verifique su algoritmo std :: sort. Es posible que ya use una ordenación introspectiva internamente.
fuente
Splaysort es un oscuro método de clasificación basado en splay trees , un tipo de árbol binario adaptativo. Splaysort es bueno no solo para datos parcialmente ordenados, sino también para datos parcialmente ordenados en reversa, o de hecho, cualquier dato que tenga algún tipo de orden preexistente. Es O (nlogn) en el caso general y O (n) en el caso en que los datos se ordenan de alguna manera (hacia adelante, hacia atrás, organo-pipe, etc.).
Su gran ventaja sobre la ordenación por inserción es que no vuelve al comportamiento O (n ^ 2) cuando los datos no están ordenados en absoluto, por lo que no necesita estar absolutamente seguro de que los datos están ordenados parcialmente antes de usarlos .
Su desventaja es la sobrecarga de espacio adicional de la estructura del árbol de extensión que necesita, así como el tiempo requerido para construir y destruir el árbol de extensión. Pero dependiendo del tamaño de los datos y la cantidad de clasificación previa que espera, la sobrecarga puede valer la pena por el aumento de la velocidad.
Se publicó un documento sobre splaysort en Software - Practice & Experience.
fuente
inserción o tipo de concha!
fuente
El smoothsort de Dijkstra es un gran tipo de datos ya ordenados. Es una variante de montón que se ejecuta en O (n lg n) en el peor de los casos y O (n) en el mejor de los casos. Yo escribí un análisis del algoritmo, en caso de que usted es curioso cómo funciona.
La combinación natural es otra muy buena para esto: es una variante de combinación ascendente que funciona tratando la entrada como la concatenación de múltiples rangos ordenados diferentes, luego usando el algoritmo de combinación para unirlos. Repite este proceso hasta que se ordene todo el rango de entrada. Esto se ejecuta en tiempo O (n) si los datos ya están ordenados y O (n lg n) en el peor de los casos. Es muy elegante, aunque en la práctica no es tan bueno como otros tipos adaptativos como Timsort o smoothsort.
fuente
Si los elementos ya están ordenados o solo hay pocos elementos, ¡sería un caso de uso perfecto para la inserción de clasificación!
fuente
La ordenación por inserción lleva tiempo O (n + el número de inversiones).
Una inversión es un par
(i, j)tal quei < j && a[i] > a[j]. Es decir, un par fuera de servicio.Una medida de estar "casi ordenado" es el número de inversiones: se podría tomar "datos casi ordenados" como datos con pocas inversiones. Si se sabe que el número de inversiones es lineal (por ejemplo, acaba de agregar elementos O (1) a una lista ordenada), la ordenación por inserción toma tiempo O (n).
fuente
Como todos los demás dijeron, tenga cuidado con Quicksort ingenuo, que puede tener un rendimiento O (N ^ 2) en datos ordenados o casi ordenados. Sin embargo, con un algoritmo apropiado para la elección del pivote (ya sea aleatorio o mediana de tres, consulte Elección de un pivote para Quicksort ), Quicksort seguirá funcionando de manera sensata.
En general, la dificultad para elegir algoritmos como la ordenación por inserción radica en decidir cuándo los datos están lo suficientemente desordenados como para que Quicksort sea realmente más rápido.
fuente
No voy a pretender tener todas las respuestas aquí, porque creo que obtener las respuestas reales puede requerir codificar los algoritmos y perfilarlos con muestras de datos representativos. Pero he estado pensando en esta pregunta toda la noche, y esto es lo que se me ha ocurrido hasta ahora, y algunas conjeturas sobre qué funciona mejor y dónde.
Sea N el número total de artículos, M sea el número fuera de servicio.
El ordenamiento de burbujas tendrá que hacer que algo como 2 * M + 1 pase por todos los N elementos. Si M es muy pequeño (0, 1, 2?), Creo que será muy difícil de superar.
Si M es pequeño (digamos menos que log N), la ordenación por inserción tendrá un gran rendimiento promedio. Sin embargo, a menos que haya un truco que no esté viendo, tendrá un rendimiento muy malo en el peor de los casos. (¿Correcto? Si el último elemento del pedido es el primero, debe insertar cada elemento, por lo que puedo ver, lo que matará el rendimiento). Supongo que hay un algoritmo de clasificación más confiable para esto. caso, pero no sé de qué se trata.
Si M es más grande (digamos igual o mayor que log N), la clasificación introspectiva es casi seguramente la mejor.
Excepción a todo eso: si realmente sabe de antemano qué elementos no están clasificados, entonces su mejor opción será extraer esos elementos, ordenarlos usando una clasificación introspectiva y fusionar las dos listas ordenadas en una sola lista ordenada. Si pudiera averiguar rápidamente qué elementos están fuera de servicio, esta también sería una buena solución general, pero no he podido encontrar una manera simple de hacerlo.
Reflexiones adicionales (de la noche a la mañana): si M + 1 <N / M, puede escanear la lista buscando una serie de N / M en una fila ordenada y luego expandir esa serie en cualquier dirección para encontrar la salida -encargar artículos. Eso tomará como máximo 2N comparaciones. A continuación, puede ordenar los elementos sin clasificar y hacer una fusión ordenada en las dos listas. Las comparaciones totales deberían ser inferiores a algo como 4N + M log2 (M), que va a superar cualquier rutina de clasificación no especializada, creo. (Aún más pensado: esto es más complicado de lo que estaba pensando, pero todavía creo que es razonablemente posible).
Otra interpretación de la pregunta es que puede haber muchos artículos fuera de servicio, pero están muy cerca de donde deberían estar en la lista. (Imagínese comenzar con una lista ordenada e intercambiar cualquier otro elemento con el que viene después). En ese caso, creo que la clasificación de burbujas funciona muy bien: creo que el número de pases será proporcional al más alejado fuera de lugar de un elemento es. La ordenación por inserción funcionará mal, porque cada elemento fuera de servicio activará una inserción. Sospecho que el tipo introspectivo o algo así también funcionará bien.
fuente
Si necesita una implementación específica para ordenar algoritmos, estructuras de datos o cualquier cosa que tenga un enlace a lo anterior, ¿podría recomendarle el excelente proyecto "Estructuras de datos y algoritmos" en CodePlex?
Tendrá todo lo que necesita sin reinventar la rueda.
Solo mi pequeño grano de sal.
fuente
Esta buena colección de algoritmos de clasificación para este propósito en las respuestas parece carecer de Gnome Sort , que también sería adecuada, y probablemente requiera el menor esfuerzo de implementación.
fuente
La ordenación por inserción es el mejor caso O (n) en la entrada ordenada. Y está muy cerca de la entrada clasificada en su mayoría (mejor que la clasificación rápida).
fuente
medita en Probar el montón. Creo que es el más consistente de los tipos O (n lg n).
fuente
El ordenamiento de burbujas (o, más seguro aún, el ordenamiento de burbujas bidireccional) es probablemente ideal para listas clasificadas en su mayoría, aunque apuesto a que un ordenamiento de peine ajustado (con un tamaño de separación inicial mucho más bajo) sería un poco más rápido cuando la lista no No tan perfectamente ordenado. La clasificación de peine se degrada a clasificación de burbujas.
fuente
bueno, depende del caso de uso. Si sabe qué elementos se cambian, eliminar e insertar será el mejor caso en lo que a mí respecta.
fuente
El tipo de burbuja es definitivamente el ganador. El siguiente en el radar sería el de inserción.
fuente
Manténgase alejado de QuickSort, es muy ineficiente para los datos previamente ordenados. La ordenación por inserción maneja bien los datos casi ordenados moviendo la menor cantidad de valores posible.
fuente