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]

The majority element isA A A C C B B C C C B C C ^ :3

`C`

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]