In the 2003 California gubernatorial recall election the bal

In the 2003 California gubernatorial recall election, the ballot contained 135 candidates, including people with various listings for their current job, including “actor,” “comedian,” and even “adult film actress.” The winner was the actor-businessman Arnold Schwarzenegger, who got over 48% of the vote. Suppose we have the election results from such an election, with a large number, n, of candidates, and the only tool we can use to determine the winner is to encode the names of all the candidates using the Huffman coding algorithm, based on the number of votes each candidate got in this election. Suppose further that a friend of yours is guessing that if the winning candidate gets more than 40% of the votes, then his or her name will be encoded with a single bit. Prove that this conjecture is true and analyze the running time of this election-counting algorithm.

Solution

In n the code for Counting sort, we are given array A[1 . . n] of length n. We required two more arrays, the array B[1 . . n] holds the sorted output and the array c[1 . . k] provides temporary working storage.

COUNTING SORT(A,B,k)

for i = 1 to k

  do c[i] = 0

for j = 1 to length[A]

  do C[A[j]] = C[A[j]] + 1

//C[i] now contains the number of elements equal to i

for i = 2 to k

  do C[i] = C[i] + C[i-1]

//C[i] now contains the number of elements less than or equal to i

for j = length[A] downto 1

  do B[C[A[j]]] = A[j]

C[A[j]] = C[A[J]] - 1

Example :

Each line below shows the step by step operation of counting sort.

Suppose that the values to be sorted are between 0 and k, where k is some (small) integer. Assume the values are in the array A[1..n].

1. Use an array C[0..k] to count how many times each key occurs in A. This requires (n) time.

2. Calculate cumulative totals in C. The time is (k). These numbers tell us, for example, that the three occurrences of 3 should be in places 5,6,7 of the nal array.

3. Copy data into the target array B. The time is (n)

for i = n downto 1   

B[C[A[i]]] A[i]

C[A[i]] C[A[i]] 1

4. Assuming k = O(n), the total time is O(n)—better than any comparison sort.