Hispanopedia WikiEn informática , la ordenación parcial es una variante relajada del problema de ordenación . La ordenación total consiste en devolver una lista de elementos tal que todos aparezcan en orden, mientras que la ordenación parcial consiste en devolver una lista de los k elementos más pequeños (o los k más grandes) en orden. Los demás elementos (por encima de los k más pequeños) también pueden ordenarse, como en una ordenación parcial in situ, o pueden descartarse, lo cual es común en las ordenaciones parciales en flujo. Un ejemplo práctico común de ordenación parcial es calcular los "100 mejores" de una lista.
En términos de índices, en una lista parcialmente ordenada, para cada índice i del 1 al k, el i -ésimo elemento está en el mismo lugar que estaría en la lista completamente ordenada: el elemento i de la lista parcialmente ordenada contiene la estadística de orden i de la lista de entrada.
Problemas sin conexión
Solución basada en montículo
Los montículos admiten una ordenación parcial simple de una sola pasada cuando k es fijo: se insertan los primeros k elementos de la entrada en un montículo máximo. Luego se realiza una pasada sobre los elementos restantes, se añade cada uno al montículo sucesivamente y se elimina el elemento más grande. Cada operación de inserción toma un tiempo de O (log k ) , lo que resulta en un tiempo total de O ( n log k ) ; este algoritmo de "ordenación parcial de montículos" es práctico para valores pequeños de k y en entornos en línea . [ 1 ] Un algoritmo de "selección de montículos en línea" descrito a continuación, basado en un montículo mínimo, toma O ( n + k log n ) . [ 1 ]
Solución mediante selección de particiones
Una relajación adicional que solo requiere una lista de los k elementos más pequeños, pero sin exigir que estén ordenados, hace que el problema sea equivalente a la selección basada en particiones ; el problema original de ordenación parcial puede resolverse mediante un algoritmo de selección de este tipo para obtener una matriz donde los primeros k elementos son los k más pequeños, y ordenarlos, con un coste total de O ( n + k log k ) operaciones. Una opción popular para implementar este esquema de algoritmo es combinar quickselect y quicksort ; el resultado a veces se denomina "quickselsort". [ 1 ]
Es común en las implementaciones actuales (a partir de 2022) de la STL de C++ un paso de heapselect para una lista de k elementos, seguido de un heapsort para el resultado final. [ 2 ]
Algoritmos de ordenación especializados
Más eficientes que los mencionados anteriormente son los algoritmos de ordenación parcial especializados basados en mergesort y quicksort . En la variante quicksort, no es necesario ordenar recursivamente las particiones que solo contienen elementos que caerían después del k -ésimo lugar en el arreglo ordenado final (comenzando desde el límite "izquierdo"). Por lo tanto, si el pivote cae en la posición k o posterior, solo aplicamos recursión a la partición izquierda: [ 3 ]
La función partial_quicksort(A, i, j, k) es si i < j entonces p ← pivote(A, i, j) p ← partición(A, i, j, p) ordenación_rápida_parcial(A, i, p-1, k) Si p < k-1, entonces partial_quicksort(A, p+1, j, k)
El algoritmo resultante se denomina ordenación rápida parcial y requiere un tiempo esperado de solo O ( n + k log k ) , siendo bastante eficiente en la práctica, especialmente si se utiliza una ordenación por selección como caso base cuando k se vuelve pequeño en relación con n . Sin embargo, la complejidad temporal en el peor de los casos sigue siendo muy alta, en el caso de una mala selección del pivote. Se podría utilizar una selección de pivote similar al algoritmo de selección de tiempo lineal en el peor de los casos (véase Quicksort § Elección del pivote ) para obtener un mejor rendimiento en el peor de los casos. La ordenación rápida parcial, la selección rápida (incluida la variante múltiple) y la ordenación rápida se pueden generalizar en lo que se conoce como ordenación por fragmentos . [ 1 ]
Clasificación incremental
La ordenación incremental es una versión del problema de ordenación parcial donde la entrada se da de antemano pero k es desconocido: dado un arreglo ordenado k , debería ser posible extender la parte parcialmente ordenada de modo que el arreglo se convierta en ordenado ( k +1) . [ 4 ]
Los montículos conducen a una solución de "selección de montículo en línea" O ( n + k log n ) para la ordenación parcial incremental: primero se "agrega en montículo", en tiempo lineal, el arreglo de entrada completo para producir un montículo mínimo. Luego se extrae el mínimo del montículo k veces. [ 1 ]
Se puede obtener una ordenación incremental diferente modificando quickselect. La versión de Paredes y Navarro mantiene una pila de pivotes entre llamadas, de modo que la ordenación incremental se puede lograr solicitando repetidamente el elemento más pequeño de un array A del siguiente algoritmo: [ 4 ]
El algoritmo IQS( A : array, i : integer, S : stack) devuelve el i -ésimo elemento más pequeño en A.
- Si i = top( S ) :
- Pop S
- Devolver A [ i ]
- Sea pivote ← aleatorio [ i , top( S ))
- Actualizar pivote ← partición( A [ i : superior( S )), A [pivote])
- Empujar el pivote hacia S
- Devuelve IQS( A , i , S )
La pila S se inicializa para contener solo la longitud n de A. La ordenación k del array se realiza llamando a IQS( A , i , S ) para i = 0, 1, 2, ... ; esta secuencia de llamadas tiene una complejidad promedio de O ( n + k log k ) , que es asintóticamente equivalente a O ( n + k log n ) . El tiempo en el peor de los casos es cuadrático, pero esto se puede solucionar reemplazando la selección aleatoria del pivote por el algoritmo de la mediana de las medianas . [ 4 ]
Apoyo lingüístico/bibliotecario
Véase también
Referencias
- 1 2 3 4 5 Conrado Martínez (2004). Sobre la ordenación parcial (PDF) . X Seminario sobre el Análisis de Algoritmos.
- ↑ "std::partial_sort" . en.cppreference.com .
- ↑ Martínez, Conrado (2004). Quicksort parcial (PDF) . Actas del 6.º Taller ACM-SIAM sobre Ingeniería de Algoritmos y Experimentos y del 1.er Taller ACM-SIAM sobre Algoritmos Analíticos y Combinatoria.
- 1 2 3 Paredes, Rodrigo; Navarro, Gonzalo (2006). "Óptima ordenación incremental". Actas del Octavo Taller sobre Ingeniería y Experimentos de Algoritmos (ALENEX) . págs. 171–182 . CiteSeerX 10.1.1.218.4119 . doi : 10.1137/1.9781611972863.16 . ISBN 978-1-61197-286-3.
Enlaces externos
- JM Chambers (1971). Clasificación parcial . CACM 14 (5):357–358.
- Algoritmos de ordenación
- Tipos en línea