En informática , la ordenación parcial es una variante relajada del problema de ordenación . La ordenación total es el problema de devolver una lista de elementos de modo que todos sus elementos aparezcan en orden, mientras que la ordenación parcial devuelve una lista de los k elementos más pequeños (o k más grandes) en orden. Los demás elementos (por encima de los k más pequeños) también se pueden ordenar, como en una ordenación parcial in situ, o se pueden descartar, lo que es común en las ordenaciones parciales en tiempo real. Un ejemplo práctico común de ordenación parcial es calcular los "100 mejores" de alguna lista.
En términos de índices, en una lista parcialmente ordenada, para cada índice i de 1 a k, el elemento i -ésimo está en el mismo lugar en el 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.
Los montículos admiten una ordenación parcial simple de una sola pasada cuando k es fijo: inserte los primeros k elementos de la entrada en un montículo máximo. Luego haga una pasada sobre los elementos restantes, agregue cada uno al montículo por turno y elimine el elemento más grande. Cada operación de inserción toma O (log k ) tiempo, 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 configuraciones 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]
Una relajación adicional que requiere solo una lista de los k elementos más pequeños, pero sin requerir que estos estén ordenados, hace que el problema sea equivalente a la selección basada en particiones ; el problema de ordenamiento parcial original se puede resolver con un algoritmo de selección de este tipo para obtener una matriz donde los primeros k elementos sean los k más pequeños, y ordenarlos, con un costo 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 llama "quickselsort". [1]
En las implementaciones actuales (a partir de 2022) de STL de C++ es común un paso de selección de montón para una lista de k elementos, seguido de una ordenación de montón para el resultado final. [2]
Más eficientes que los mencionados anteriormente son los algoritmos de ordenamiento parcial especializados basados en mergesort y quicksort . En la variante quicksort, no hay necesidad de ordenar recursivamente particiones que solo contienen elementos que caerían después del k 'ésimo lugar en la matriz ordenada final (empezando por el límite "izquierdo"). Por lo tanto, si el pivote cae en la posición k o posterior, recurramos solo en 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 ordenación rápida parcial (A, p+1, j, k)
El algoritmo resultante se denomina quicksort parcial y requiere un tiempo esperado de solo O ( n + k log k ) , y es bastante eficiente en la práctica, especialmente si se utiliza un ordenamiento por selección como caso base cuando k se vuelve pequeño en relación con n . Sin embargo, la complejidad temporal del peor caso sigue siendo muy mala, en el caso de una mala selección de pivote. La selección de pivote en las líneas del algoritmo de selección temporal lineal del peor caso (consulte Quicksort § Elección del pivote ) podría usarse para obtener un mejor rendimiento en el peor de los casos. El quicksort parcial, la selección rápida (incluida la variante múltiple) y el quicksort pueden generalizarse en lo que se conoce como chunksort . [1]
La ordenación incremental es una versión del problema de ordenación parcial donde la entrada se proporciona por adelantado pero se desconoce k : dada una matriz ordenada en k , debería ser posible extender la parte parcialmente ordenada para que la matriz quede ordenada en ( k +1) . [4]
Los montones conducen a una solución de "selección de montón en línea" O ( n + k log n ) para la ordenación parcial incremental: primero, "amontonar", en tiempo lineal, la matriz de entrada completa para producir un montón mínimo. Luego, extraer el mínimo del montón 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 una matriz A del siguiente algoritmo: [4]
El algoritmo IQS( A : matriz, i : entero, S : pila) devuelve el i -ésimo elemento más pequeño en A
La pila S se inicializa para contener solo la longitud n de A . La ordenación k de la matriz se realiza llamando a IQS( A , i , S ) para i = 0, 1, 2, ... ; esta secuencia de llamadas tiene una complejidad de caso promedio O ( n + k log k ) , que es asintóticamente equivalente a O ( n + k log n ) . El tiempo del peor caso es cuadrático, pero esto se puede solucionar reemplazando la selección de pivote aleatorio por el algoritmo de la mediana de las medianas . [4]
std::partial_sort.nlargesty nsmallesten su heapqmódulo.PartialQuickSortalgoritmo utilizado en partialsort!y variantes.