admin 管理员组

文章数量: 1184232

Counting sort assumes that each of the n input elements is an integer in the range 0 to k , for some integer k. When k=O(n), the sort runs in Θ(n) time.
The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into position in the output array. For example, if there are 17 elements less than x, then x belongs in output position 18.This scheme must be modified slightly to handle the situation in which several elements have the same value, since we don’t want to put them all in the same position.

COUNTING-SORT(A,B,K)
for i <- 0 to k
    do C[i]<-0
for j<- 1 to length[A]
    do C[A[j]]<-C[A[j]]+1
for i<- 1 to k
    do C[i]<-C[i]+C[i-1]
for j<- length[A] downto 1
    do B[C[A[j]]<-A[j]
       C[A[j]]<-C[A[j]]-1

An important property of counting sort is that it is stable, counting sort’s stability is crucial to radix sort’s correctness.

Exercises 8.2-1

Using Figure 8.2 as a model, illustrate the operation of COUNTING-SORT on the array A=[6,0,2,0,1,3,4,6,1,3,2]

Exercises 8.2-2

Prove that COUNTING-SORT is stable.
Becasue we put element in B array is from end to begin( j<- length[A] downto 1), and then we Subtraction C[A[j]], so the numbers have same value ,wo put them front of it .

Exercises 8.2-3

Suppose that the for loop header in line 9 of the COUNTING-SORT procedure is rewritten as 

9  for j<- 1 to length[A]

Show that the algorithm still works properly. Is the modified algorithm stable?

Notice that the correctness argument in the text does not depend on the order in
which A is processed. The algorithm is correct no matter what order is used!
But the modiÞed algorithm is not stable. As before, in the Þnal for loop an element
equal to one taken from A earlier is placed before the earlier one (i.e., at a lower
index position) in the output arrray B. The original algorithm was stable because
an element taken from A later started out with a lower index than one taken earlier.
But in the modiÞed algorithm, an element taken from A later started out with a
higher index than one taken earlier.
In particular, the algorithm still places the elements with value k in positions
C[k − 1] + 1 through C[k], but in the reverse order of their appearance in A.

Exercises 8.2-4

Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range[a,b] in O(1) time.
Your algorithm should use Θ(n+k) preprocessing time.

Compute the C array as is done in counting sort. The number of integers in the
range [a . . b] is C[b] − C[a − 1], where we interpret C[−1] as 0.

本文标签： Counting sort

版权声明：本文标题：Counting sort 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1758311158a3084308.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。