BFPRT

In informatica, BFPRT (Blum, Floyd, Pratt, Rivest, Tarján) è un algoritmo in quattro passi, utile alla selezione dell'ennesimo elemento più piccolo di un array disordinato.

Algoritmo

1. Raccogli gli elementi dell'array in gruppi di 5. Se il numero di elementi dell'array non è un multiplo di 5, crea un ulteriore gruppo (che conterrà al massimo 4 elementi).
2. Trova il mediano di ciascun gruppo.
3. Tramite una chiamata ricorsiva, trova il mediano dei mediani.
4. Usa il mediano dei mediani M come perno e richiama l'algoritmo ricorsivamente sull'array opportuno, esattamente come nell'algoritmo quickselect.

Voci correlate

• Quickselect