Majority Vote Problem · boro741/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

‎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

0 commit comments

Comments
 (0)