The Boyer-Moore Majority Vote Algorithm

Question

I have started learning Java recently and was looking into some easy algorithms. I found the Boyer Moore voting algorithm here.

I am trying to get better at writing good code for my solutions. Please give me your suggestions.

import java.util.Scanner;
public class MajorityVoteAlgorithm {
 public static void main(String[] args) {
 Scanner keyboard = new Scanner(System.in);
 int size = keyboard.nextInt(); // define size of array
 int[] array = new int[size];
 // initialize array
 for (int i = 0; i < array.length; i++) {
 array[i] = keyboard.nextInt();
 }
 majorityelement(array);
 }
 private static void majorityelement(int[] array) {
 int count = 0;
 int candidate = 0;
 for (int i = 0; i < array.length; i++) {
 if (count == 0) {
 candidate = array[i]; 
 // set the count as 1
 count = 1;
 continue;
 } else if (candidate == array[i])
 count++;
 else {
 count--;
 }
 }
 if (count == 0) {
 System.out.println("No majority element found");
 } else {
 // set the count to zero to count the occurrence of the candidate
 count = 0;
 for (int i = 0; i < array.length; i++) {
 if (candidate == array[i])
 count++;
 }
 if (count > array.length / 2)
 System.out.println("Majority element is " + candidate);
 else
 System.out.println("No majority element found");
 }
 }
}

Answer 1

• int[] is too strong a requirement. The code does not do any random access. Consider changing an argument from array to stream (this way you may process data not fitting in memory).

• The method does two (technically) unrelated jobs: finding the maybe dominant element, and verification that the element is indeed dominant. I recommend splitting it into two methods, for the following reasons:

  • Each loop does an important job and deserves a name.

  • If it is guaranteed that the dominant element exists, verification is a waste of time.

  • If it is guaranteed that the dominant element exists, the requirements can be relaxed even more to an input iterator.

• Do not print anything from the algorithm. Let main handle results.

Answer 2

Interesting algorithm.

The implementation seems correct, handling corner cases such as empty array and array with one element correctly.

Aside from that, though, you should work on using braces consistently, not just where necessary. Your current style is minimalistic and doesn't allow easy visual parsing.

Whenever you use an algorithm that has a name, write the name in a comment in either your function description or an implementation. Also include a link if you can, to save someone a google search.

• Dhrubojyoti Bhattacharjee: Thanks, I will kep that in mind. I have already included a link with my question.

Answer 3

Adding to already given inputs, instead of running the loop of counting the occurrences and then checking the count, handle the corner case - only one element in array first. That saves time if there is only one element

• 200_success: Please explain why a one-element array should be a special case? What would that code look like?