Hispanopedia Wiki
Articulo de referencia

Algoritmo de Floyd-Rivest

1/2 log 1/2 ''n'')}}"},"time":{"wt":""},"space":{"wt":""}},"i":0}}]}"> En informática , el algoritmo de Floyd-Rivest es un algoritmo de selección desarrollado por Robert W. Floy...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el algoritmo de Floyd-Rivest es un algoritmo de selección desarrollado por Robert W. Floyd y Ronald L. Rivest que tiene un número óptimo esperado de comparaciones dentro de los términos de orden inferior . Es funcionalmente equivalente a quickselect , pero en la práctica se ejecuta más rápido 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 log 1/2 n ) .

El algoritmo se presentó originalmente en un informe técnico de la Universidad de Stanford de 1973 que contenía dos artículos, donde se le denominó SELECT y se asoció con PICK, o mediana de medianas . [ 2 ] Posteriormente se publicó en Communications of the ACM , volumen  18, número  3.

Algoritmo

El algoritmo de Floyd-Rivest es un algoritmo de divide y vencerás , que comparte muchas similitudes con quickselect . Utiliza el muestreo para dividir la lista en tres conjuntos. Luego, selecciona recursivamente el k -ésimo elemento más pequeño del conjunto correspondiente.

Los pasos generales son:

  1. Seleccione una pequeña muestra aleatoria S de la lista L.
  2. A partir de S , seleccione recursivamente dos elementos u y v , de manera que u < v . Estos dos elementos serán los pivotes para la partición y se espera que contengan el k -ésimo elemento más pequeño de toda la lista entre ellos (en una lista ordenada).
  3. Usando u y v , particione 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 .
  4. Divida los elementos restantes en L (es decir, los elementos en L \ S ) comparándolos con u o v y colocándolos 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 primero con v 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 .  
  5. Basándose en el valor de k , aplique el algoritmo recursivamente al conjunto apropiado para seleccionar el k -ésimo elemento más pequeño en L.

Al usar | S | = Θ( n 2/3 log 1/3 n ), podemos obtener n + min( k , n − k ) + O ( n 2/3 log 1/3 n ) comparaciones esperadas. Podemos obtener n + min( k , n − k ) + O ( n 1/2 log 1/2 n ) comparaciones esperadas comenzando con un S pequeño y actualizando repetidamente u y v para mantener el tamaño de B suficientemente pequeño ( O ( n 1/2 log 1/2 n ) en Θ( n ) elementos procesados) sin riesgo inaceptable de que el elemento deseado esté fuera de B .

Versión en pseudocódigo

El siguiente pseudocódigo reorganiza los elementos entre lefty right, de tal manera 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, siendo el i-ésimo elemento menor o igual que el k- ésimo para todo left≤ i ≤ k y siendo el j-ésimo elemento mayor o igual que para k ≤ j ≤ right:

// left es el índice izquierdo del intervalo // right es el índice derecho del intervalo // k es el valor del índice deseado, donde array[k] es el (k+1)-ésimo elemento más pequeño cuando left = 0 function select(array, left, right, k) is while right > left do // Usar select recursivamente para muestrear un conjunto más pequeño de tamaño s // Las constantes arbitrarias 600 y 0.5 se utilizan en la versión original // para minimizar el tiempo de ejecución. if right − left > 600 then 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) × sign (i − n/2) nuevoIzquierda := max (izquierda, k − i × s/n + sd) nuevoDerecha := min (derecha, k + (n − i) × s/n + sd) seleccionar (array, nuevoIzquierda, nuevoDerecha, k) // divide los elementos entre izquierda y derecha alrededor de t t := array[k] yo := izquierda j := derecha Intercambiar array[left] y array[k] si array[right] > t entonces intercambiar array[right] y array[left] mientras i < j hacer intercambiar array[i] y array[j] i := i + 1 j := j − 1 mientras array[i] < t hacer i := i + 1 mientras array[j] > t hacer j := j − 1 Si array[left] = t, entonces intercambie array[left] y array[j]; de lo contrario j := j + 1 Intercambiar array[j] y array[right] // Ajustar izquierda y derecha hacia los límites del subconjunto // que contiene el (k − izquierda + 1)-ésimo elemento más pequeño. Si j ≤ k entonces izquierda := j + 1 si k ≤ j entonces derecha := j − 1

Véase también

Referencias

  1. ↑ 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 . S2CID 122069429 .  
  2. ↑ Dos artículos sobre el problema de selección: Límites de tiempo para la selección y Límites de tiempo esperados para la selección (PDF) (Informe técnico). Informes técnicos y notas técnicas de informática de Stanford. Abril de 1973. CS-TR-73-349.
  • Floyd, Robert W.; Rivest , Ron L. (marzo de 1975). "Límites de tiempo esperados para la selección" (PDF) . Communications of the ACM . 18 (3): 165–172 . doi : 10.1145/360680.360691 . S2CID 3064709 . 
  • Kiwiel, Krzysztof C. (30 de noviembre de 2005). "Sobre el algoritmo SELECT de Floyd y Rivest" (PDF) . Theoretical Computer Science . 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". International Journal of Computer Mathematics . 82 (5): 509– 519. CiteSeerX 10.1.1.7.8672 . doi : 10.1080/00207160512331331048 . S2CID 16522119 .