Analysis & Design of Algorithms

Counting Sort • Prepared by:-

Sagar Virani

Assistant Professor

Computer Engineering
Department

VVP Engineering College

 Counting Sort
• It is a non-comparative sorting algorithm.

• Assumption: 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).

• Example:
• Input: <4, 1, 3, 4, 3>
• n = 5 and k = 4
 Counting Sort
• It determines, for each input element x, the number less than x.
• Using this information, the algorithm place’s x directly into its position
in the output array.

• Example:
• If 17 elements are less than x, then x belongs to position 18 in the
output array.
 Counting Sort
• The algorithm uses three arrays:

• Input array: A[1…n] stores input data.

• Output array: B[1…n] stores the sorted data.
• Temporary array: C[0…k] provides temporary working storage.
 Counting Sort

Input list

2 5 3 0 2 3 0 3
 Counting Sort

A 2 5 3 0 2 3 0 3

0 1 2 3 4 5

C 0 0 0 0 0 0
 Counting Sort

A 2 5 3 0 2 3 0 3 • Count number of 0’s from the

input array and put at C[0].
0 1 2 3 4 5

C 2 0 0 0 0 0
 Counting Sort

A 2 5 3 0 2 3 0 3 • Count number of 1’s from the

input array and put at C[1].
0 1 2 3 4 5

C 2 0 0 0 0 0
 Counting Sort

A 2 5 3 0 2 3 0 3 • Count number of 2’s from the

input array and put at C[2].
0 1 2 3 4 5

C 2 0 2 0 0 0
 Counting Sort

A 2 5 3 0 2 3 0 3 • Count number of 3’s from the

input array and put at C[3].
0 1 2 3 4 5

C 2 0 2 3 0 0
 Counting Sort

A 2 5 3 0 2 3 0 3 • Count number of 4’s from the

input array and put at C[4].
0 1 2 3 4 5

C 2 0 2 3 0 0
 Counting Sort

A 2 5 3 0 2 3 0 3 • Count number of 5’s from the

input array and put at C[5].
0 1 2 3 4 5

C 2 0 2 3 0 1
 Counting Sort

A 2 5 3 0 2 3 0 3 • Add C[0] and C[1] and put

the cumulative sum at C[1].
0 1 2 3 4 5

C 2 0 2 3 0 1

Addition
 Counting Sort

A 2 5 3 0 2 3 0 3 • Add C[1] and C[2] and put

the cumulative sum at C[2].
0 1 2 3 4 5

C 2 2 2 3 0 1

Addition
 Counting Sort

A 2 5 3 0 2 3 0 3 • Add C[2] and C[3] and put

the cumulative sum at C[3].
0 1 2 3 4 5

C 2 2 4 3 0 1

Addition
 Counting Sort

A 2 5 3 0 2 3 0 3 • Add C[3] and C[4] and put

the cumulative sum at C[4].
0 1 2 3 4 5

C 2 2 4 7 0 1

Addition
 Counting Sort

A 2 5 3 0 2 3 0 3 • Add C[4] and C[5] and put

the cumulative sum at C[5].
0 1 2 3 4 5

C 2 2 4 7 7 1

Addition
 Counting Sort

A 2 5 3 0 2 3 0 3

0 1 2 3 4 5

C 2 2 4 7 7 8
 Counting Sort

1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3

0 1 2 3 4 5
• Take auxiliary array B (empty array)
C 2 2 4 7 7 8
whose size is equal to size of A.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B

• Start a loop from last element of A.

0 1 2 3 4 5

C 2 2 4 7 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B

• Take value of last element and use it

0 1 2 3 4 5
as index to array C.
C 2 2 4 7 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 2 2 4 7 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 3

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 2 2 4 7 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 3

• Decrement the loop variable.

0 1 2 3 4 5

C 2 2 4 6 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 3

• Take value of second last element

0 1 2 3 4 5
and use it as index to array C.
C 2 2 4 6 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 3

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 2 2 4 6 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 2 2 4 6 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3

• Decrement the loop variable.

0 1 2 3 4 5

C 1 2 4 6 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3

• Take value of third last element and

0 1 2 3 4 5
use it as index to array C.
C 1 2 4 6 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 1 2 4 6 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3 3

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 1 2 4 6 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3 3

• Decrement the loop variable.

0 1 2 3 4 5

C 1 2 4 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3 3

• Take value of fourth last element

0 1 2 3 4 5
and use it as index to array C.
C 1 2 4 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 3 3

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 1 2 4 5 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 2 3 3

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 1 2 4 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 2 3 3

• Decrement the loop variable.

0 1 2 3 4 5

C 1 2 3 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 2 3 3

• Take value of fifth last element and

0 1 2 3 4 5
use it as index to array C.
C 1 2 3 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 2 3 3

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 1 2 3 5 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 1 2 3 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3

• Decrement the loop variable.

0 1 2 3 4 5

C 0 2 3 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3

• Take value of sixth last element and

0 1 2 3 4 5
use it as index to array C.
C 0 2 3 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 0 2 3 5 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 0 2 3 5 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3

• Decrement the loop variable.

0 1 2 3 4 5

C 0 2 3 4 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3

• Take value of seventh last element

0 1 2 3 4 5
and use it as index to array C.
C 0 2 3 4 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 0 2 3 4 7 8 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3 5

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 0 2 3 4 7 8
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3 5

• Decrement the loop variable.

0 1 2 3 4 5

C 0 2 3 4 7 7
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3 5

• Take value of first element and use it

0 1 2 3 4 5
as index to array C.
C 0 2 3 4 7 7
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 3 3 3 5

• Take value of array C and use it as

0 1 2 3 4 5
index to array B.
C 0 2 3 4 7 7 • Put the value of last element in array
B at the index found.
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 2 3 3 3 5

• Decrement the value of element in

0 1 2 3 4 5
array C.
C 0 2 3 4 7 7
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 2 3 3 3 5

• Decrement the loop variable.

0 1 2 3 4 5
Not possible.
C 0 2 2 4 7 7
 Counting Sort

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3 B 0 0 2 2 3 3 3 5

Sorted!!!

0 1 2 3 4 5

C 0 2 2 4 7 7
 Counting Sort
Algorithm
COUNTING-SORT(A, B, k)
let C[0…..k] be a new array
for i = 0 to k
C[ i ] = 0
for j = 1 to A.length
C[ A[ j ] ] = C[ A[ j ] ] + 1
for i =1 to k
C[ i ] = C[ i ] + C[ i – 1 ]
for j = A.length downto 1
B[C[ A[ j ] ] ] = A[ j ]
C[ A[ j ] ] = C[ A[ j ] ] – 1
 Counting Sort
Analysis
COUNTING-SORT(A, B, k)
let C[0…..k] be a new array
for i = 0 to k Θ(k)

C[ i ] = 0
for j = 1 to A.length Θ(n)

C[ A[ j ] ] = C[ A[ j ] ] + 1
for i =1 to k Θ(k)
C[ i ] = C[ i ] + C[ i – 1 ]
for j = A.length downto 1 Θ(n)

B[C[ A[ j ] ] ] = A[ j ] Total: Θ(n + k)

C[ A[ j ] ] = C[ A[ j ] ] – 1
 Counting Sort
Advantages
• Simple implementation.
• Provides stable sorting.
• Takes linear time to sort the input.
• Running time: O(n + k)
 Counting Sort
Disadvantages
• Doesn’t provide in-place sorting.
• Requires additional memory space to sort.

• Generally used as an intermediate step in other sorting

algorithms.
 Pseudo code for Counting sort
Algorithm
COUNTING-SORT (A, B, n, k)
{
let C[k] be a new array
for i = 0 to k
C[ i ] = 0
for j = 1 to n
C[ A[ j ] ] = C[ A[ j ] ] + 1
for i =1 to k
C[ i ] = C[ i ] + C[ i – 1 ]
for j = n downto 1
B[C[ A[ j ] ] ] = A[ j ]
C[ A[ j ] ] = C[ A[ j ] ] – 1
}
Any Questions?