X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 11 / 28

108 views

0 shares

0 downloads

0 comments

11 / 28

Comp 122

linsort - 11

Lin / Devi

Comp 122

Counting-Sort (A, B, k)

CountingSort(A, B, k)

1.  for i 0 to k

2.        do C[i] 0

3.  for j 1 to length[A]

4.        do C[A[j]] C[A[j]] + 1

5.  for i 1 to k

6.        do C[i] C[i] + C[i –1]

7.  for j length[A] downto 1

8.        do B[C[A[ j ]]] A[j]

9.             C[A[j]] C[A[j]]–1

O(k)

O(k)

O(n)

O(n)

Document info
Document views108
Page views108
Page last viewedTue Jan 24 09:21:25 UTC 2017
Pages28
Paragraphs427
Words1924

Comments