Algoritmus Floyd – Rivest - Floyd–Rivest algorithm

v počítačová věda, Algoritmus Floyd-Rivest je algoritmus výběru vyvinutý uživatelem Robert W. Floyd a Ronald L. Rivest který má optimální očekávaný počet srovnání v rámci podmínky nižšího řádu. Je funkčně ekvivalentní s rychlý výběr, ale v praxi běží v průměru rychleji.^[1] Má očekávanou provozní dobu Ó(n) a očekávaný počet srovnání n + min (k, n − k) + Ó(n^1/2).

Algoritmus byl původně představen v technické zprávě Stanfordské univerzity obsahující dva dokumenty, kde byl označován jako VYBRAT a spárovat s PICK, nebo medián mediánů.^[2] Následně byla zveřejněna v Komunikace ACM, Svazek 18: Vydání 3.

Algoritmus

Algoritmus Floyd-Rivest je a algoritmus rozděl a panuj, sdílení mnoho podobností s rychlý výběr. Využívá to vzorkování který pomůže rozdělit seznam na tři sady. Potom rekurzivně vybere kten nejmenší prvek z příslušné množiny.

Obecné kroky jsou:

1. Vyberte malý náhodný vzorek S ze seznamu L.
2. Z S, rekurzivně vybrat dva prvky, u a proti, takový, že u < proti. Tyto dva prvky budou čepy pro oddíl a očekává se, že budou obsahovat knejmenší prvek celého seznamu mezi nimi (v seřazeném seznamu).
3. Použitím u a proti, oddíl S do tří sad: A, B, a C. A bude obsahovat prvky s hodnotami menšími než u, B bude obsahovat prvky s hodnotami mezi u a proti, a C bude obsahovat prvky s hodnotami většími než proti.
4. Rozdělte zbývající prvky do L (tj. prvky v L - S) jejich porovnáním s u nebo proti a umístit je do příslušné sady. Li k je menší než polovina počtu prvků v L zaokrouhleno nahoru, pak by měly být porovnány zbývající prvky proti nejprve a pak jen do u pokud jsou menší než proti. Jinak by měly být zbývající prvky porovnány s u první a jediný proti pokud jsou větší než u.
5. Na základě hodnoty k, použijte algoritmus rekurzivně na příslušnou sadu a vyberte kth nejmenší prvek v L.

Verze pseudokódu

Následující pseudo kód seřadí prvky mezi vlevo, odjet a že jo ve vzestupném pořadí, tak, že pro nějakou hodnotu k, kde vlevo, odjet ≤ k ≤ že jo, kten prvek v seznamu bude obsahovat (k − vlevo, odjet + 1) nejmenší hodnota:

// left je levý index intervalu// right je pravý index pro daný interval// k je požadovaná hodnota indexu, kde pole [k] je (k + 1) th nejmenší prvek, když vlevo = 0funkce vyberte (pole, vlevo, vpravo, k) je    zatímco že jo > vlevo, odjet dělat        // Použijte select rekurzivně ke vzorkování menší sady velikostí s        // v originálu jsou použity libovolné konstanty 600 a 0,5        // verze pro minimalizaci doby provedení.        -li vpravo - vlevo> 600 pak            n: = vpravo - vlevo + 1 i: = k - vlevo + 1 z: = ln(n) s: = 0,5 × exp(2 × z / 3) sd: = 0,5 × čtv(z × s × (n - s) / n) × podepsat(i - n / 2) newLeft: = max(vlevo, k - i × s / n + sd) newRight: = min(vpravo, k + (n - i) × s / n + sd) vybrat(pole, newLeft, newRight, k) // rozdělit prvky mezi levou a pravou kolem t        t: = pole [k] i: = vlevo j: = vpravo vyměnit pole [vlevo] a pole [k] -li pole [vpravo]> t pak            vyměnit pole [vpravo] a pole [vlevo] zatímco i dělat            vyměnit pole [i] a pole [j] i: = i + 1 j: = j - 1 zatímco pole [i] dělat                i: = i + 1 zatímco pole [j]> t dělat                j: = j - 1 -li pole [vlevo] = t pak            vyměnit pole [vlevo] a pole [j] jiný            j: = j + 1 vyměnit pole [j] a pole [vpravo] // Upravte doleva a doprava směrem k hranicím podmnožiny        // obsahující (k - levý + 1) ten nejmenší prvek.        -li j ≤ k pak            vlevo: = j + 1 -li k ≤ j pak            vpravo: = j - 1

Viz také

• Quickselect
• Introselect
• Medián mediánů

Reference