Boyer-Moore většinový hlasovací algoritmus je algoritmus pro nalezení dominantního prvku v sekvenci. Převažujícím prvkem posloupnosti délky n je prvek této posloupnosti, který se v ní vyskytuje více než n/2krát. Složitost tohoto algoritmu je O(n) a požadovaná dodatečná paměť je O(1).
Algoritmus je pojmenován po R. Boyerovi a Jay Moore , kteří jej publikovali v roce 1981. [jeden]
Algoritmus vyžaduje zavedení dvou dalších proměnných: první bude obsahovat prvek posloupnosti, který je nejvhodnější pro roli převládajícího prvku z těch, které již byly uvažovány, a druhá je čítač a zpočátku se rovná nule. Algoritmus sestává z jednoho průchodu uvažovanou sekvencí. V každém kroku se provádějí následující akce: pokud je aktuální hodnota proměnné čítače nula, pak se tento prvek sekvence zapíše do první proměnné a čítač se rovná 1. Pokud je hodnota čítače jiná než nula , pak se aktuální prvek sekvence porovná s hodnotou zapsanou do první proměnné. Pokud se shodují, počítadlo se zvýší o 1, jinak se sníží o 1.
Pseudokód algoritmu :
Po zvážení všech prvků bude první proměnná obsahovat dominantní prvek sekvence, pokud nějaký existuje. Pokud však takový prvek v sekvenci není, pak první proměnná bude stále obsahovat nějaký prvek sekvence. Pokud tedy neexistuje jistota, že dominantní prvek existuje, měl by být proveden další průchod polem, aby se zajistilo, že se nalezený prvek v poli vyskytuje více než n/2krát. Pokud se v důsledku druhého průchodu ukáže, že prvek se nevyskytuje více než n/2krát, pak posloupnost dominantního prvku neobsahuje. [2]