stringtranslate.com

Algoritmo de Floyd-Rivest

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 quickselect , 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 log 1/2 n ) .

El algoritmo se presentó originalmente en un informe técnico de la Universidad de Stanford que contenía dos artículos, donde se lo denominaba SELECT y se lo emparejaba 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 división y conquista , que comparte muchas similitudes con quickselect . Utiliza el muestreo para ayudar a dividir la lista en tres conjuntos. Luego selecciona de forma recursiva el k -ésimo elemento más pequeño del conjunto apropiado.

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 , tales 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 , divide 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. Particionar 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. En función del valor de k , aplique el algoritmo de forma recursiva 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 una S pequeña y actualizando repetidamente u y v para mantener el tamaño de B lo suficientemente pequeño ( O ( n 1/2 log 1/2 n ) en Θ( n ) elementos procesados) sin un riesgo inaceptable de que el elemento deseado esté fuera de B .

Versión de pseudocódigo

El siguiente pseudocódigo reorganiza los elementos entre lefty right, de modo que para algún valor k , donde left≤ k ≤ right, el k ésimo elemento en la lista contendrá el ( k − left+ 1) ésimo valor más pequeño, con el i ésimo elemento siendo menor o igual que el k ésimo para todos left≤ i ≤ k y el j ésimo elemento siendo mayor o igual que para k ≤ j ≤ right:

// left es el índice izquierdo para el intervalo
// right es el índice derecho para el intervalo
// k es el valor de í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 // Use select recursivamente para muestrear un conjunto más pequeño de tamaño s // las constantes arbitrarias 600 y 0.5 se usan 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 := en (n) s := 0,5 × exp (2 × z/3) sd := 0,5 × raíz cuadrada (z × s × (n − s)/n) × signo (i − n/2) newLeft := máx (izquierda, k − i × s/n + sd) newRight := min (derecha, k + (n − i) × s/n + sd) seleccionar (matriz, newLeft, newRight, k) // particionar los elementos entre izquierda y derecha alrededor de t t := matriz[k] yo := me fui j := correcto intercambia array[izquierda] y array[k] si array[derecha] > t entonces  intercambia array[derecha] y array[izquierda] mientras i < j intercambia array[i] y array[j ] yo := yo + 1 j := j − 1 mientras array[i] < t hacer yo := yo + 1 mientras array[j] > t hacer j := j − 1 si array[izquierda] = t entonces  intercambia array[izquierda] y array[j] de lo contrario j := j + 1 Intercambia array[j] y array[right] // Ajuste a la izquierda y a la 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 la selección: Límites de tiempo para la selección y Límites de tiempo esperados para la selección (PDF) (informe técnico). Stanford Computer Science Technical Reports and Technical Notes. Abril de 1973. CS-TR-73-349.