requisitos de iterador de órdenes rápidas

Question

tl; dr: ¿Es posible implementar quicksort en una lista doblemente enlazada de manera eficiente? Mi entendimiento antes de pensarlo fue, no, no lo es.

El otro día tuve la oportunidad de considerar los requisitos del iterador para los algoritmos básicos de clasificación. Los O (N²) básicos son bastante sencillos.

• Tipo de burbuja - 2 iteradores de ida funcionarán muy bien, arrastrando uno tras otro.
• Tipo de inserción: 2 iteradores bidireccionales funcionarán. Uno para el elemento fuera de servicio, uno para el punto de inserción.
• Clasificación de selección: un poco más complicado pero los iteradores de avance pueden hacer el truco.

ordenación rápida

El introsort_loop en std :: sort (como en la biblioteca/CV estándar de GNU (1994)/Silicon Graphics (1996)) requiere que se le random_access.

__introsort_loop(_RandomAccessIterator __first, 
     _RandomAccessIterator __last, 
     _Size __depth_limit, _Compare __comp) 

Como he llegado a esperar.

Ahora, luego de una inspección más cercana, no puedo encontrar el motivo real para requerir esto para el quicksort. Lo único que requiere explícitamente random_access_iterators es la llamada std::__median que requiere que se calcule el elemento intermedio. La solución estándar de vainilla no calcula la mediana.

La partición consiste en un cheque

if (!(__first < __last)) 
    return __first; 

No

realmente un eficaz control de una bidirectionals. Sin embargo uno debe ser capaz de reemplazar esto con un cheque en el viaje de partición anterior (de izquierda a derecha/derecha a izquierda) con una simple condición de

if (__first == __last) this_partitioning_is_done = true; 

¿Es posible implementar la clasificación rápida bastante eficiente utilizando iteradores única bidireccionales ? La profundidad recursiva aún puede ser protegida.

NB. Todavía no he intentado una implementación real.

Answer 1

tl; dr: Sí

Como usted dice, el problema es encontrar el elemento pivote, que es el elemento en el medio, encontrando esto con acceso aleatorio toma O (1), encontrándolo con Los iteradores bidireccionales toman O (n) (n/2 operaciones, para ser precisos). Sin embargo, en cada paso debe crear subcontenedores, el izquierdo y el derecho con números más pequeños y más grandes, respectivamente. Aquí es donde tiene lugar el trabajo principal de clasificación rápida, ¿verdad?

Ahora, al construir los contenedores secundarios (para el paso de recursión) mi enfoque sería crear un iterador h apuntando a su elemento frontal respectivo.Ahora cada vez que elija un elemento siguiente para ir al contenedor secundario, simplemente avance h cada segundo tiempo. Esto tendrá h apunta al elemento de pivote una vez que esté listo para descender al nuevo paso de recursión.

Solo tiene que encontrar el primer pivote que realmente no importa, porque O (n log n + n/2) = O (n log n).

En realidad esto es solo una optimización en tiempo de ejecución, pero no tiene impacto en la complejidad, ya sea si repite la lista una vez (para poner cada valor en el contenedor secundario respectivo) o dos veces (para encontrar el pivote y luego ponga cada valor en el contenedor secundario respectivo) es todo lo mismo: O (2n) = O (n).
Es simplemente una cuestión de tiempo de ejecución (no de complejidad).

Answer 2

Necesita iteradores de acceso aleatorio porque normalmente desea elegir el elemento pivote del centro de la lista. Si elige el primer elemento o el último como pivote, los iteradores bidireccionales son suficientes, pero luego Quicksort degenera a O (n^2) para las listas ordenadas previamente.

Answer 3

No hay ningún problema con la implementación de la estrategia de ordenación rápida en una lista doblemente vinculada. (Creo que también se puede adaptar fácilmente a una lista de enlace único). El único lugar en el algoritmo de clasificación rápida tradicional que depende del requisito de acceso aleatorio es la fase de configuración que utiliza algo "complicado" para seleccionar el elemento pivote. En realidad, todos estos "trucos" no son más que heurísticas que pueden ser reemplazadas por métodos secuenciales bastante efectivos.

He implementado la ordenación rápida para listas vinculadas anteriormente. No tiene nada de especial, solo tiene que prestar mucha atención al enlace de elementos adecuado. Como probablemente entienda, gran parte del valor de los algoritmos de ordenación de listas proviene del hecho de que puede reordenar elementos por , volviendo a vincular, en lugar de un intercambio de valores explícito. No solo podría ser más rápido, sino que también (y con frecuencia, lo que es más importante) preserva la validez de valor de las referencias externas que podrían adjuntarse a los elementos de la lista.

P.S. Sin embargo, diría que para las listas vinculadas, el algoritmo de clasificación combina una implementación significativamente más elegante, que tiene un rendimiento igualmente bueno (a menos que se trate de algunos casos que funcionan mejor con la ordenación rápida específicamente).