BFPRT

Abbozzo
Questa voce sull'argomento algoritmi è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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

[modifica | modifica wikitesto]
  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

[modifica | modifica wikitesto]
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica