Tipo estable y eficiente?

Question

estoy tratando de crear una aplicación inusual conjunto asociativo que es muy eficiente con el espacio, y necesito un algoritmo de ordenación que cumpla con todos los siguientes:

1. estable (no cambia el orden relativo de los elementos con igualdad de teclas.)
2. en el lugar o casi en el lugar (o (log n) pila está bien, pero no o (n) de uso del espacio o montón asignaciones.
3. o (N log N) complejidad del tiempo.

También tenga en cuenta que la estructura de datos que se ordenará es un arra y

Es fácil ver que hay un algoritmo básico que coincide con cualquiera de estos dos (inserción tipo coincide con 1 y 2, fusión tipo coincide con 1 y 3, tipo de ordenamiento coincide con 2 y 3), pero no puedo por la vida de yo encuentro cualquier cosa que coincida con los tres de estos criterios.

Answer 1

¿Qué pasa con el quicksort?

Exchange también lo puede hacer, puede ser más "estable" según sus términos, pero el quicksort es más rápido.

Answer 2

Merge sort se puede escribir para estar en el lugar, creo. Esa puede ser la mejor ruta.

Answer 3

¿Quizás shell sort? Si recuerdo correctamente el curso de estructuras de datos, tendía a ser estable, pero peor es que el tiempo es O (n log^2 n), aunque realiza O (n) en datos casi ordenados. Se basa en la ordenación por inserción, por lo que se ordena en su lugar.

Answer 4

Hay una lista de algoritmos de ordenamiento en Wikipedia. Incluye categorización por tiempo de ejecución, estabilidad y asignación.

Probablemente su mejor opción sea la de modificar una clasificación eficiente e inestable para que sea estable, lo que la hace menos eficiente.

Answer 5

Nota: quicksort estándar es no O (n log n)! En el peor de los casos, puede llevar hasta O (n^2) tiempo. El problema es que puede pivotar en un elemento que está lejos de la mediana, por lo que sus llamadas recursivas están muy desequilibradas.

Hay una forma de combatir esto, que consiste en elegir cuidadosamente una mediana que esté garantizada, o al menos muy probablemente, cerca de la mediana. Es sorprendente que pueda encontrar la mediana exacta en tiempo lineal, aunque en su caso parece que le preocupa la velocidad, por lo que no lo sugeriría.

creo que el enfoque más práctico es implementar una clasificación rápida estable (es fácil de mantener estable) pero el uso de la mediana de 5 valores aleatorios como el pivote en cada paso. Esto hace que sea muy poco probable que tenga una clasificación lenta y que sea estable.

Por cierto, el tipo de combinación se puede realizar en el lugar, aunque es complicado hacer tanto en el lugar como estable.

Answer 6

Hay una clase de algoritmos de fusión in situ estables, aunque son complicados y lineales con una constante bastante alta oculta en el O (n). Para obtener más información, eche un vistazo a this article, and its bibliography.

Editar: la fase de fusión es lineal, por lo tanto, el mergesort es nlog_n.

Answer 7

No se preocupe demasiado por O (n log n) hasta que pueda demostrar que es importante. Si puede encontrar un algoritmo O (n^2) con una constante drásticamente menor, ¡adelante!

El peor escenario general no es relevante si sus datos están muy restringidos.

En resumen: Ejecute algunas pruebas.

Answer 8

Como sus elementos están en una matriz (en lugar de, por ejemplo, una lista vinculada) tiene información sobre su orden original disponible para usted en los índices de la matriz. Usted puede tomar ventaja de esto escribiendo sus funciones de clasificación y comparación para estar al tanto de los índices:

function cmp(ar, idx1, idx2) 
{ 
    // first compare elements as usual 
    rc = (ar[idx1]<ar[idx2]) ? -1 : ((ar[idx1]>ar[idx2]) ? 1 : 0); 

    // if the elements are identical, then compare their positions 
    if(rc != 0) 
     rc = (idx1<idx2) ? -1 : ((idx1>idx2) ? 1 : 0); 

    return rc; 
} 

Esta técnica se puede utilizar para hacer cualquier tipo estable, siempre que el tipo sólo realiza permutas de elementos. Los índices de los elementos cambiarán, pero el orden relativo de los elementos idénticos se mantendrá igual, por lo que la clasificación sigue siendo robusta. No funcionará de la caja para un tipo como heapsort porque la heapificación original "descarta" el orden relativo, aunque es posible que puedas adaptar la idea a otros géneros.

Answer 9

Quicksort se puede hacer estable de forma razonablemente sencilla simplemente añadiendo un campo de secuencia a cada registro, inicializándolo en el índice antes de clasificarlo y usándolo como la parte menos importante de la clave de ordenación.

Esto tiene un efecto levemente adverso en el tiempo empleado pero no afecta la complejidad de tiempo del algoritmo. También tiene una sobrecarga de costo de almacenamiento mínimo para cada registro, pero eso rara vez es importante hasta que obtiene un gran número de registros (y se mimetiza con registros de mayor tamaño).

He usado este método con la función Cqsort() para evitar escribir la mía. Cada registro tiene un número entero de 32 bits agregado y poblado con el número de secuencia inicial antes de llamar al qsort().

Luego la función de comparación verificó las claves y la secuencia (esto garantiza que no hay llaves duplicadas), convirtiendo el quicksort en uno estable. Recuerdo que aún superaba el mergesort inherentemente estable para los conjuntos de datos que estaba usando.

Su rendimiento puede variar, así que siempre recuerde: ¡Mida, no adivine!

Answer 10

Tal vez estoy en un poco de rutina, pero me gusta el tipo de fusión con código de mano. Es simple, estable y de buen comportamiento. El almacenamiento temporal adicional que necesita es solo N*sizeof(int), lo que no está nada mal.

Answer 11

Hay una buena lista de funciones de clasificación on wikipedia que pueden ayudarlo a encontrar el tipo de función de clasificación que desee.

Por ejemplo, para abordar su pregunta específica, parece que una ordenación de fusión in situ es lo que desea.

Sin embargo, también es posible que desee echar un vistazo a strand sort, tiene algunas propiedades muy interesantes.

Answer 12

Quicksort puede hacerse estable al hacerlo en una lista vinculada. Esto cuesta n seleccionar aleatoria o mediana de 3 pivotes pero con una constante muy pequeña (recorrido de lista).

Al dividir la lista y asegurarse de que la lista de la izquierda se ordena para que los mismos valores queden a la izquierda y la lista correcta para que los mismos valores vayan bien, la clasificación será implícita estable sin costo adicional real. Además, como se trata de asignación en lugar de intercambio, creo que la velocidad podría ser un poco mejor que una ordenación rápida en una matriz, ya que solo hay una sola escritura.

Así que en conclusión, una lista de todos sus elementos y ejecutar la clasificación rápida en una lista

Answer 13

he implementado un stable in-place quicksort y una stable in-place merge sort. El tipo de combinación es un poco más rápido y se garantiza que funciona en O (n * log (n)^2), pero no en la ruta rápida. Ambos usan el espacio O (log (n)).