Scribd
Upload
3 views35 pages

Week 7 - Counting Sort

Counting sort is an integer sorting algorithm that operates on a fixed range of input values from 0 to k. It uses three arrays: an input array to store the data, an output array for the sorted data, and a temporary array to count occurrences of each value. The algorithm counts the number of elements less than or equal to each input element to determine their position in the output array.

Uploaded by

kkzara418
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views35 pages

Week 7 - Counting Sort

Counting sort is an integer sorting algorithm that operates on a fixed range of input values from 0 to k. It uses three arrays: an input array to store the data, an output array for the sorted data, and a temporary array to count occurrences of each value. The algorithm counts the number of elements less than or equal to each input element to determine their position in the output array.

Uploaded by

kkzara418
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting Algorithms

Counting sort
 Counting sort assumes that each of the n input elements is an
integer in the range 0 to k. that is n is the number of elements and
k is the highest value element.
 Consider the input set : 4, 1, 3, 4, 3. Then n=5 and k=4
 Counting sort determines for each input element x, the number of
elements less than or equal to x. And it uses this information to
place element x directly into its position in the output array. For
example if there exits 17 elements less that x then x is placed into
the 18th position into the outputarray.
 The algorithm uses three array:
Input Array: A[1..n] store input data where A[j]  {1, 2, 3, …, k}
Output Array: B[1..n] finally store the sorted data
Temporary Array: C[0..k] store data temporarily
Counting Sort
1. Counting-Sort(A, B, k)
2. Let C[0…..k] be a new array
3. for i=0 to k
4. C[i]= 0;
5. for j=1 to [Link] or n
6. C[ A[j] ] = C[ A[j] ] + 1;
7. for i=1 to k
8. C[i] = C[i] +C[i-1];
9. for j=n or [Link] down to 1
10. B[ C[ A[j] ] ] = A[j];
11. C[ A[j] ] = C[ A[j] ] - 1;
Counting Sort
1. Counting-Sort(A, B, k)
2. Let C[0…..k] be a new array
[Link] i=0 to k [Loop 1]
4. C[i]= 0;
[Link] j=1 to [Link]( or n) 6. [Loop 2]
C[ A[j] ] = C[ A[j] ] +1;
[Link] i=1 to k [Loop 3]
8. C[i] = C[i] +C[i-1];
[Link] j=n or [Link] down to 1 [Loop 4]
10. B[ C[ A[j] ] ] = A[j];
11. C[ A[j] ] = C[ A[j] ] - 1;
Counting-sort example
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C:

1 2 3 4 5 6 7 8

B:
Executing Loop 1
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 00 00 00 00 00 00

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 00 00 1 00 00 00

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 5 33 00 22 33 00 33

0 1 2 3 4 5

C: 00 00 11 00 00 1

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 3 00 22 33 00 33

0 1 2 3 4 5

C: 00 00 11 1 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 33 0 22 33 00 33

0 1 2 3 4 5

C: 1 00 11 11 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 33 00 2 33 00 33

0 1 2 3 4 5

C: 11 00 2 11 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 33 00 22 3 00 33

0 1 2 3 4 5

C: 11 00 22 2 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 0 33

0 1 2 3 4 5

C: 2 00 22 22 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 2
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 3

0 1 2 3 4 5

C: 22 00 22 3 00 11

1 2 3 4 5 6 7 8

B:
End of Loop2
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 22 00 22 33 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 3
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 2 0 22 33 00 11
0 1 2 3 4 5

C: 22 2 22 33 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 3
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 22 2 2 33 00 11
0 1 2 3 4 5

C: 22 22 4 33 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 3
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 22 22 4 3 00 11
0 1 2 3 4 5

C: 22 22 44 7 00 11

1 2 3 4 5 6 7 8

B:
Executing Loop 3
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 22 22 44 7 0 11
0 1 2 3 4 5

C: 22 22 44 77 7 11

1 2 3 4 5 6 7 8

B:
Executing Loop 3
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 22 22 44 77 7 1
0 1 2 3 4 5

C: 22 22 44 77 77 8

1 2 3 4 5 6 7 8

B:
End of Loop3
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 33

0 1 2 3 4 5

C: 22 22 44 77 77 88

1 2 3 4 5 6 7 8

B:
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 3

0 1 2 3 4 5

C: 22 22 44 7 77 88

1 2 3 4 5 6 7 8

B:
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 00 3

J=8,then A[ j ]=A[8]=3
0 1 2 3 4 5 And B[ C[A[j] ] ]
=B[ C[3 ] ]
C: 22 22 44 7 77 88 =B[ 7]
So B[ C[ A[j] ] ] ←A[ j ]
=B[7]←3

1 2 3 4 5 6 7 8

B:
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 33 00 22 33 0 33

J=8,then A[ j ]=A[8]=3
0 1 2 3 4 5 Then C[A[j]]
= C[ 3]
C: 2 22 44 6 77 88 =7
So C[A[j] ] = C[A[j] ]-1
=7-1=6

1 2 3 4 5 6 7 8

B: 33
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 33 00 22 3 00 33

0 1 2 3 4 5

C: 11 22 44 6 77 88

1 2 3 4 5 6 7 8

B: 00 33
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 33 00 2 33 00 33

0 1 2 3 4 5

C: 11 22 4 55 77 88

1 2 3 4 5 6 7 8

B: 00 33 33
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 33 0 33 00 33

0 1 2 3 4 5

C: 1 22 33 55 77 88

1 2 3 4 5 6 7 8

B: 00 22 33 33
Executing Loop 4
1 2 3 4 5 6 7 8

A: 55 3 0 33 00 33

0 1 2 3 4 5

C: 00 22 33 5 77 88

1 2 3 4 5 6 7 8

B: 00 00 22 33 33
Executing Loop 4
1 2 3 4 5 6 7 8

A: 5 33 0 33 00 33

0 1 2 3 4 5

C: 00 22 33 44 77 8

1 2 3 4 5 6 7 8

B: 00 00 22 33 33 33
Executing Loop 4
1 2 3 4 5 6 7 8

A: 2 55 33 0 33 00 33

0 1 2 3 4 5

C: 00 22 3 44 77 77

1 2 3 4 5 6 7 8

B: 00 00 22 33 33 33 55
End of Loop4
1 2 3 4 5 6 7 8

A: 55 33 0 33 00 33

0 1 2 3 4 5

C: 00 22 22 44 77 77

1 2 3 4 5 6 7 8

B: 00 00 22 22 33 33 33 55

Sorted data in Array B


Time Complexity Analysis
1. Counting-Sort(A, B, k)
2. Let C[0…..k] be a new array
Loop 1 and 3
[Link] i=0 to k [Loop 1] takes O(k) time
4. C[i]= 0;
5. for j=1 to [Link] or n [Loop 2]
6. C[ A[j] ] = C[ A[j] ] + 1;
7. for i=1 to k [Loop 3]
8. C[i] = C[i] +C[i-1];
9. for j=n or [Link] down to 1 [Loop 4]
10. B[ C[ A[j] ] ] = A[j]; Loop 2 and 4
takes O(n) time
11. C[ A[j] ] = C[ A[j] ] - 1;
Time Complexity Analysis
• So the counting sort takes a total time of: O(n +k)
• Counting sort is called stable sort.
– A sorting algorithm is stable when numbers with
the same values appear in the output array in the
same order as they do in the input array.
Counting Sort Review
• Assumption: input taken from small set of numbers of size n
• Basic idea:
– Count number of elements less than or equal to a particular
element and do this for each of the elements.
– This gives the position of that number –similar to selection
• sort.
Pro’s:
– Fast
– Asymptotically fast - O(n+k)
• –Simple to code
Con’s:
– Doesn’t sort in place.
– Requires O(k) extra storage.

You might also like