structures examples data algorithm language-agnostic data-structures sorting

algorithm - examples - ¿Tipo estable y eficiente?



data structures arrays (13)

¿Qué hay de quicksort?

Exchange también puede hacer eso, puede ser más "estable" según sus términos, pero la oferta rápida es más rápida.

Intento crear una implementación de matriz asociativa inusual que sea muy eficiente en el uso del espacio, y necesito un algoritmo de ordenamiento que cumpla con todo lo siguiente:

  1. Estable (no cambia el orden relativo de los elementos con las mismas teclas).
  2. En el lugar o casi in situ (la pila O (log n) está bien, pero no el uso de espacio O (O) o las asignaciones de pila.
  3. O (n log n) complejidad del tiempo.

También tenga en cuenta que la estructura de datos que se ordenará es una matriz.

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, fusiona ordenando coincide 1 y 3, agrupamiento ordena 2 y 3), pero no puedo encontrar nada que coincide con los tres de estos criterios.

Existe 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 este artículo y su bibliografía .

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

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

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

Tal vez tipo de concha ? 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.

Nota : ¡la orden rápida estándar no es 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 manera 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 puedas encontrar la mediana exacta en tiempo lineal, aunque en tu caso parece que te preocupa la velocidad, así que no te lo sugiero.

Creo que el enfoque más práctico es implementar un quicksort estable (es fácil mantenerse estable) pero use la mediana de 5 valores aleatorios como 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 fusión se puede realizar in situ, aunque es complicado hacer tanto en el lugar como estable.

El tipo de combinación se puede escribir para estar en el sitio, creo. Esa puede ser la mejor ruta.

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: ejecutar alguna prueba.

Debido a que 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. Puede aprovechar esto escribiendo sus funciones de clasificación y comparación para conocer 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 usar para hacer que cualquier tipo sea estable, siempre que el género SÓLO realice intercambios 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 sólida. 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.

Quicksort puede hacerse bastante estable de forma 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 significativa de la clave de clasificación.

Esto tiene un efecto levemente adverso en el tiempo empleado pero no afecta la complejidad del 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 qsort() C para evitar escribir el mío. Cada registro tiene un número entero de 32 bits agregado y rellenado con el número de secuencia inicial antes de llamar a qsort() .

Luego, la función de comparación verificó las teclas y la secuencia (esto garantiza que no hay claves 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 millaje puede variar, así que siempre recuerde: ¡ Mida, no adivine!

Hay una buena lista de funciones de clasificación en wikipedia que pueden ayudarte a encontrar el tipo de función de clasificación que buscas.

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

Sin embargo, es posible que también desee ver el tipo de cadena , tiene algunas propiedades muy interesantes.

Tal vez estoy en una especie de rutina, pero me gusta el tipo de combinación codificada a mano. Es simple, estable y de buen comportamiento. El almacenamiento temporal adicional que necesita es solo N*sizeof(int) , lo cual no está nada mal.

Quicksort se puede estabilizar haciéndolo 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 asegurar que la lista de la izquierda esté ordenada de manera que los mismos valores queden a la izquierda y la lista correcta esté ordenada de manera que los mismos valores vayan bien, la clasificación será implícitamente 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.

Por lo tanto, en conclusión, enumere todos sus artículos y ejecute quicksort en una lista