A A A C C B B C C C B C C
 ^
?:0

We will sweep down the sequence starting at the pointer position shown above.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

Click on Step below to carry out the algorithm.

[Step]

[Abort]

 

  A A A C C B B C C C B C C
   ^
  A:1

[Step]

[Abort]

 

  A A A C C B B C C C B C C
     ^
    A:2

[Step]

[Abort]

 

  A A A C C B B C C C B C C
       ^
      A:3

[Step]

[Abort]

 

  A A A C C B B C C C B C C
         ^
        A:2

[Step]

[Abort]

 

  A A A C C B B C C C B C C
           ^
          A:1

[Step]

[Abort]

 

  A A A C C B B C C C B C C
             ^
            ?:0

[Step]

[Abort]

 

  A A A C C B B C C C B C C
               ^
              B:1

[Step]

[Abort]

 

  A A A C C B B C C C B C C
                 ^
                ?:0

[Step]

[Abort]

 

  A A A C C B B C C C B C C
                   ^
                  C:1

[Step]

[Abort]

 

  A A A C C B B C C C B C C
                     ^
                    C:2

[Step]

[Abort]

 

  A A A C C B B C C C B C C
                       ^
                      C:1

[Step]

[Abort]

 

  A A A C C B B C C C B C C
                         ^
                        C:2

[Step]

[Abort]

 

  A A A C C B B C C C B C C 
                           ^
                          C:3

Note that if you replaced the first C with an A, above, the algorithm would still end with C being chosen, but in fact C would not be the majority element: there is no majority in the modified list.

In some situations you know, or assume, there is a majority element.

But if you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.

[Return to Majority Page]







































[end of example]