ypxu / MajorityVoting.java

Created January 13, 2012


    
    View MajorityVoting.java 
  
  
      MajorityVoting.java
    
    
        Raw
      
    
    File suppressed. Click to show.
  
  
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
          
          
            import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class MajorityVoting {
 
	public static String checkForWinner(List<String> votes) {
		String winner = "Nobody";
		String[] votesArr = votes.toArray(new String[votes.size()]);
		if (votesArr == null || votesArr.length == 0) {
			return winner;
		}
 
		String[] sortedResult = quickSort(votesArr);
		String currentVote = "";
		int voteCount = 0;
		int maxVote = 0;
		for (int index = 0; index < sortedResult.length; index++) {
			if (currentVote == "") {
				currentVote = sortedResult[index];
			}
			if (currentVote.equalsIgnoreCase(sortedResult[index])) {
				voteCount++;
			} else {
				if (voteCount > maxVote) {
					maxVote = voteCount;
					winner = currentVote;
				}
				voteCount = 1;
				currentVote = sortedResult[index];
			}
		}
		return 2 * maxVote > sortedResult.length ? winner : "Nobody";
	}
 
	private static String[] quickSort(String[] array) {
		int len = array.length;
		internalQuickSort(array, 0, len);
		return array;
	}
 
	private static void internalQuickSort(String[] array, int left, int right) {
		if (left < right) {
			int pivot = (right + left) / 2;
			int newSplitPoint = partition(array, left, right, pivot);
			internalQuickSort(array, left, newSplitPoint - 1);
			internalQuickSort(array, newSplitPoint + 1, right);
		}
 
	}
 
	private static int partition(String[] array, int left, int right, int pivot) {
		String temp = array[pivot];
		array[pivot] = array[left];
		array[left] = temp;
 
		pivot = left;
		for (int index = left + 1; index < right; index++) {
			if (array[index].hashCode() < array[pivot].hashCode()) {
				String tempVal = array[pivot];
				array[pivot] = array[index];
				array[index] = tempVal;
				pivot = index;
			}
		}
		return pivot;
	}
}