Finding Leader Algorithm

We name Leader, an element which appears in set more than half of the times. In our example we are not going to count who will become the president of US, algorithm makes sense for more than 2 candidates. Our example can be election on nomination in the Democratic Party. Let's start! We have a set Y where we have votes, for candidates in Kentucky state. Let's give each candidate a number.

To Y set, we will put some fake data, each number, means the vote for candidate, that has this number. Y={2,1,3,2,2,2,4,2,1} We can solve problem by many methods, for example caunting occurences of each of number in set, but it's verry labor-intensive, in points I will write how to find a leader, in the easiest way. In Steps 1-5 we will find a candidate for a leader, by eliminating other candidates, and than we will chceck if our candidate appears more than half times in our set.

Finding Leader Algorithm: Data: Set Y of n elements {x1,x2,...,xn}

Result: Leader l in a Y set, or information, that set Y don't have a leader.

Step 1. Set x1 as leader l and c:=1

{Steps 2-5: Here we are choosing a candidate for a leader in set Y.}

Step 2. For next values of set i= 2, 3, ..., n follow steps 3-5, next go to step 6.

Step 3. If c = 0, follow step 4, otherwise proceed to step 5.

Step 4. {We pick new candidate for leader}. Take xi as a leader l, and c:=1.

Step 5. {We are comparing the next element of set with candidate for the leader.} If xi=l, c+=1, otherwise c-=1.

{Steps 6-8: We are cheeking if l is trutly a leader in set Y.}

Step 6. If c=0, proceed to step 7, otherwise follow step 8.

Step 7. Y set hasn't got a leader. End algorithm.

Step 8. Count occurance of l in Y set. If it's bigger than n/2, l is a leader, otherwise Y set, does not contain a leader.

C++ code:

int main()
{

int Y [9] = { 2,1,3,2,2,2,4,2,1 };

//step 1
int c = 1;
int l = Y[0];
//setp 2
for(int i=1;i<9;++i)
	{
		//step 3
		if(c == 0)
			{
				//step 4
				l=Y[i];
				c=1;
			}
			else
			{
				//step 5
				if(Y[i]==l) c++;
				else c--;
			}
	}

//step 6
if(c==0)
	{
		//step 7
		cout<<"Y set doesn't have a leader."<<endl;
	}
	else
	{
		//step 8
		int counter=0;
		for(int i=0;i<9;++i) { if(Y[i]==l) counter++; } if(counter>=5) cout<<"The leader is:"<<l;
		else cout<<"Y set doesn't have a leader."<<endl;

	}

return 0;
}