Sorting in linear time Counting sort: no comparisons between elements Input:A[l..nl, where a∈{1,2,…,k} Output: B[1.nI, sorted Auxiliary storage: C[l. k o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.11
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.11 Sorting in linear time Counting sort: No comparisons between elements. • Input: A[1 . . n], where A[j]∈{1, 2, …, k} . • Output: B[1 . . n], sorted. • Auxiliary storage: C[1 . . k]
Counting sort for it to k d0C[d←0 for i<I to n do calil<-ClAlill+1 bcli- lkey=i for it2 to k do c[i<Ci+ Cli-l b Cli- key si forj←- n downto l doBC[4j←A[ C[A[小←C[A[-1 o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.12
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.12 Counting sort for i ← 1 to k do C[i] ← 0 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| for i ← 2 to k do C[i] ← C[i] + C[i–1] ⊳ C[i] = |{key ≤ i}| for j ← n downto 1 do B[C[A[ j]]] ← A[ j] C[A[ j]] ← C[A[ j]] – 1
Counting-sort example 2345 4 A:41343 B: o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5. 13
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.13 Counting-sort example A: 44 11 33 44 33 B: 12345 C: 1234
Loop 1 2345 1234 A:41343 C:0000 B: for i<1 to k d0C[←0 o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.14
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.14 Loop 1 A: 44 11 33 44 33 B: 12345 C: 00 00 00 00 1234 for i ← 1 to k do C[i] ← 0
L00p2 2345 4 A:41343 C:0001 B: for i<I to n do calil< CAlil+I b cli- rkey=i o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.15
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.15 Loop 2 A: 44 11 33 44 33 B: 12345 C: 00 00 00 11 1234 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|