En informática , el algoritmo Floyd-Rivest es un algoritmo de selección desarrollado por Robert W. Floyd y Ronald L. Rivest que tiene un número esperado óptimo de comparaciones dentro de términos de orden inferior . Es funcionalmente equivalente a la selección rápida , pero se ejecuta más rápido en la práctica en promedio. [1] Tiene un tiempo de ejecución esperado de O ( n ) y un número esperado de comparaciones de n + min ( k , n - k ) + O ( n 1/2 ).
Clase | Algoritmo de selección |
---|---|
Estructura de datos | Formación |
Rendimiento medio | n + mínimo ( k , norte - k ) + O ( norte 1/2 ) |
El algoritmo se presentó originalmente en un informe técnico de la Universidad de Stanford que contenía dos artículos, donde se denominó SELECT y se emparejó con PICK, o mediana de medianas . [2] Posteriormente se publicó en Communications of the ACM , Volumen 18: Número 3.
Algoritmo
El algoritmo Floyd-Rivest es un algoritmo de divide y vencerás , que comparte muchas similitudes con la selección rápida . Utiliza el muestreo para ayudar a dividir la lista en tres conjuntos. A continuación, selecciona de forma recursiva el k- ésimo elemento más pequeño del conjunto apropiado.
Los pasos generales son:
- Seleccionar una pequeña muestra aleatoria S de la lista L .
- De S , seleccione recursivamente dos elementos, u y v , de manera que u < v . Estos dos elementos serán los pivotes de la partición y se espera que contengan el k- ésimo elemento más pequeño de la lista completa entre ellos (en una lista ordenada).
- El uso de u y v , partición de S en tres conjuntos: A , B , y C . A contendrá los elementos con valores menores que u , B contendrá los elementos con valores entre u y v , y C contendrá los elementos con valores mayores que v .
- Partición de los elementos restantes en L (es decir, los elementos en L - S ) comparándolos con u o v y colocarlos en el conjunto apropiado. Si k es menor que la mitad del número de elementos en L redondeado hacia arriba, entonces los elementos restantes deben compararse av primero y luego solo con u si son menores que v . De lo contrario, los elementos restantes deben compararse primero con u y solo con v si son mayores que u .
- Basándose en el valor de k , aplicar el algoritmo de forma recursiva para el conjunto apropiado para seleccionar el k -ésimo elemento más pequeño de L .
Versión de pseudocódigo
El siguiente pseudocódigo ordena los elementos entre left
y right
en orden ascendente, de modo que para algún valor k , donde left
≤ k ≤ right
, el k- ésimo elemento de la lista contendrá el ( k - left
+ 1) -ésimo valor más pequeño:
// izquierda es el índice de la izquierda para el intervalo // derecha es el índice de la derecha para el intervalo // k es el valor de índice deseado, donde matriz [k] es el (k + 1) elemento más pequeño cuando left = 0 selección de función (array, left, right, k) es while right > left do // Use select recursivamente para muestrear un conjunto más pequeño de tamaños s // las constantes arbitrarias 600 y 0.5 se usan en la versión // original para minimizar el tiempo de ejecución. si derecha - izquierda> 600 entonces n: = derecha - izquierda + 1 i: = k - izquierda + 1 z: = ln (n) s: = 0.5 × exp (2 × z / 3) sd: = 0.5 × sqrt (z × s × (n - s) / n) × signo (i - n / 2) newLeft: = max (izquierda, k - i × s / n + sd) newRight: = min (right, k + (n - i) × s / n + sd) select (array, newLeft, newRight, k) // divide los elementos entre izquierda y derecha alrededor de t t: = matriz [k] i: = izquierda j: = derecha intercambio array [izquierdo] y array [k] si array [derecha]> t luego de intercambio array [right] y array [Izquierda] mientras que ihacer intercambio array [i] y array [j] yo: = yo + 1 j: = j - 1 while array [i] hacer yo: = yo + 1 while array [j]> t hacer j: = j - 1 si matriz [izquierda] = t entonces intercambia matriz [izquierda] y matriz [j] si no j: = j + 1 intercambiar matriz [j] y matriz [derecha] // Ajusta a izquierda y derecha hacia los límites del subconjunto // que contiene el (k - left + 1) th elemento más pequeño. si j ≤ k entonces izquierda: = j + 1 si k ≤ j entonces derecha: = j - 1
Ver también
Referencias
- ^ Floyd, Robert W .; Rivest, Ronald L. (1975). "Algoritmo 489: El algoritmo SELECT - para encontrar el i-ésimo más pequeño de n elementos" (PDF) . Comm. ACM . 18 (3): 173. CiteSeerX 10.1.1.309.7108 . doi : 10.1145 / 360680.360694 .
- ^ Dos artículos sobre el problema de la selección: Plazos para la selección y Plazos previstos para la selección (PDF) (Informe técnico). Informes técnicos y notas técnicas de Stanford Computer Science . Abril de 1973. CS-TR-73-349.
- Floyd, Robert W .; Rivest, Ron L. (marzo de 1975). "Límites de tiempo previstos para la selección" (PDF) . Comunicaciones de la ACM . 18 (3): 165-172. doi : 10.1145 / 360680.360691 .
- Kiwiel, Krzysztof C. (30 de noviembre de 2005). "Sobre el algoritmo SELECT de Floyd y Rivest" (PDF) . Informática Teórica . 347 (1–2): 214–238. doi : 10.1016 / j.tcs.2005.06.032 .
- Gerbessiotis, Alexandros V .; Siniolakis, Constantinos J .; Paraskevi, Aghia (mayo de 2005). "Un análisis probabilístico del algoritmo de selección de tiempo esperado de Floyd-Rivest". Revista Internacional de Matemáticas Informáticas . 82 (5): 509–519. CiteSeerX 10.1.1.7.8672 .