BFPRT

Da Wikipedia, l'enciclopedia libera.

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

Algoritmo[modifica | modifica sorgente]

  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 sorgente]


informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica