Came across this interesting algorithm. Used for knowing the contestant with the majority in a voting.
Say professors McGonagall, Snape, Flitwick and Sprout are all contesting to be the next headmaster/headmistress at Hogwarts, after Dumbledore.
All the students are given a choice to vote for their favourite professor.
The common approach is segregating the votes based on the contestant, counting each group and finally deciding the leader.
But in majority voting, the contestant has to get more than half the number of votes. That’s what this algorithm is for.
So let’s say we like to do majority voting i.e. any of the 4 professors needs to have more than half the number of students voting for them.
Here’s how the voting goes:
Initially count is 0. leader is None. Students are casting their votes as follows:
Dean Thomas’s vote: McGonagall => count becomes 1 (increment, since leader is None yet), leader becomes McGonagall.
Seamus Finnigan’s vote: McGonagall => count becomes 2. (increment, since it’s the same contestant again)
Draco Malfoy’s vote: Snape (obviously 😉 ) => count becomes 1 (decrement, since it’s a different contestant)
Neville Longbottom’s vote: Sprout => count becomes 0 (decrement, since it’s a different contestant again)
Hermione Granger’s vote: Flitwick => leader becomes Flitwick (since count is 0).count becomes 1 (since current vote is the same as for leader).
Ron Weasley’s vote: Flitwick => count becomes 2 (increment, since it’s the same contestant again)
Harry Potter’s vote: McGonagall => count becomes 1 (decrement, since it’s a different contestant)
….
….
….
Thus, all the students cast their votes. Not imagining all their votes here 😛
Get the idea?
- Initially,
countis set to 0 andleaderis set to no one. - The contestant who got the first vote is set to
leaderandcountis incremented. countkeeps incrementing as long as the current vote is for the same contestant.- If it’s for a different contestant,
countdecrements. - At any point of time, if
countbecomes 0,leaderis reset to current vote’s contestant and the algorithm continues. - At the end, whichever contestant
leaderis set to, they’re declared the winner of the majority voting contest.
This algorithm is based on the clever idea of cancellation of votes, if a diffent contestant comes up for the next vote.
Very ingenius of Mr Boyer and Mr Moore !
P.S. Who do you think became the next headmaster/headmistress of Hogwarts? My bet is on McGonagall 😉
Leave a Reply