Visitar URL original
Majority Vote Problem · zzhgithub/AlgorithmVisualizer@3de3211 · GitHub
Skip to content

Commit 3de3211

Browse files
archie94archie94
committed
Majority Vote Problem
1 parent 17b0a94 commit 3de3211

4 files changed

Lines changed: 83 additions & 1 deletion

File tree

‎algorithm/category.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,8 @@
4646
},
4747
"greedy": {
4848
"list": {
49-
"job_scheduling": "Job Scheduling Problem"
49+
"job_scheduling": "Job Scheduling Problem",
50+
"majority_element": "Majority Element(Boyer–Moore majority vote algorithm)"
5051
},
5152
"name": "Greedy"
5253
},

‎algorithm/greedy/majority_element/basic/code.js‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
function isMajorityElement ( element ) {
2+
var count = 0;
3+
logger._print ('Verify majority element ' + element );
4+
for (var i = N - 1; i >= 0; i--) {
5+
tracer._notify (i,A[i])._wait ();
6+
if (A[i] == element) {
7+
count++;
8+
} else {
9+
tracer._denotify (i);
10+
}
11+
}
12+
logger._print ('Count of our assumed majority element ' + count);
13+
if(count>Math.floor (N/2)) {
14+
logger._print ('Our assumption was correct!');
15+
return true;
16+
}
17+
logger._print ('Our assumption was incorrect!');
18+
return false;
19+
}
20+
21+
function findProbableElement () {
22+
var index = 0, count = 1;
23+
tracer._select (index)._wait();
24+
logger._print ('Beginning with assumed majority element : ' + A[index] + ' count : ' +count);
25+
logger._print ('--------------------------------------------------------');
26+
for( var i = 1; i < N; i++ ) {
27+
tracer._notify (i,A[i])._wait ();
28+
if(A[index]==A[i]) {
29+
count++;
30+
logger._print ('Same as assumed majority element! Count : ' + count);
31+
} else {
32+
count--;
33+
logger._print ('Not same as assumed majority element! Count : ' + count);
34+
}
35+
36+
if(count===0) {
37+
logger._print ('Wrong assumption in majority element');
38+
tracer._deselect (index);
39+
tracer._denotify (i);
40+
index = i;
41+
count = 1;
42+
tracer._select (i)._wait ();
43+
logger._print ('New assumed majority element!'+ A[i] +' Count : '+count);
44+
logger._print ('--------------------------------------------------------');
45+
} else {
46+
tracer._denotify (i);
47+
}
48+
}
49+
logger._print ('Finally assumed majority element ' + A[index]);
50+
logger._print ('--------------------------------------------------------');
51+
return A[index];
52+
}
53+
54+
function findMajorityElement () {
55+
var element = findProbableElement ();
56+
if(isMajorityElement (element) === true) {
57+
logger._print ('Majority element is ' + element);
58+
} else {
59+
logger._print ('No majority element');
60+
}
61+
}
62+
63+
findMajorityElement ();

‎algorithm/greedy/majority_element/basic/data.js‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
var A = [ 1, 3, 3, 2, 1, 1, 1 ];
2+
var N = A.length;
3+
4+
var tracer = new Array1DTracer('List of element')._setData (A);
5+
var logger = new LogTracer ('Console');

‎algorithm/greedy/majority_element/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Majority Element(Boyer–Moore majority vote algorithm)": "The majority vote problem is to determine in any given sequence of choices whether there is a choice with more occurrences than half of the total number of choices in the sequence and if so, to determine this choice.",
3+
"Complexity": {
4+
"time": " O(N)",
5+
"space": "O(logN)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Find majority element in array using Boyer–Moore majority vote algorithm"
12+
}
13+
}

0 commit comments

Comments
 (0)