BFPRT

Această intrare pe tema algoritmilor este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

În informatică , BFPRT ( Blum , Floyd , Pratt , Rivest , Tarján ) este un algoritm în patru pași, util pentru selectarea celui de-al n-lea cel mai mic element dintr-o matrice dezordonată.

Algoritm

1. Colectați elementele matricei în grupuri de 5. Dacă numărul elementelor din matrice nu este multiplu de 5, creați un grup suplimentar (care va conține maximum 4 elemente).
2. Găsiți mediana fiecărui grup.
3. Folosind un apel recursiv, găsiți mediana medianelor.
4. Folosește mediana medianelor M ca pivot și apelează algoritmul recursiv pe matricea corespunzătoare, la fel ca în algoritmul de selectare rapidă .

Elemente conexe

• Selectare rapidă

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel

Portal IT : accesați intrările Wikipedia care se ocupă cu IT