DAA
National Institute of Science & Technology
An Introduction to
Algorithm
Dr. Sudhir Ranjan Pattanaik [1]
DAA Counting Sort
The Algorithm
National Institute of Science & Technology
Counting-Sort(A)
Initialize two arrays B and C of size n and set all entries to 0
Count the number of occurrences of every A[i]
for i = 1..n
do C[A[i]] ← C[A[i]] + 1
Count the number of occurrences of elements <= A[i]
for i = 2..n
do C[i] ← C[i] + C[i – 1]
Move every element to its final position
for i = n..1
do B[C[A[i]] ← A[i]
C[A[i]] ← C[A[i]] – 1
Dr. Sudhir Ranjan Pattanaik
DAA Counting Sort Example
1 2 3 4 5 6 7 8
National Institute of Science & Technology
A= 2 5 3 0 2 3 0 3
0 1 2 3 4 5
C= 2 0 2 3 0 1
0 1 2 3 4 5
C= 2 2 4 7 7 8
1 2 3 4 5 6 7 8
B= 3
0 1 2 3 4 5
C= 2 2 4 67 7 8
Dr. Sudhir Ranjan Pattanaik
DAA Counting Sort Example
National Institute of Science & Technology
1 2 3 4 5 6 7 8
A= 2 5 3 0 2 3 0 3
0 1 2 3 4 5
C= 2 2 4 6 7 8
1 2 3 4 5 6 7 8
B= 0 3
0 1 2 3 4 5
C= 21 2 4 6 7 8
Dr. Sudhir Ranjan Pattanaik
DAA
Counting Sort Example
National Institute of Science & Technology
1 2 3 4 5 6 7 8
A= 2 5 3 0 2 3 0 3
0 1 2 3 4 5
C= 2 2 4 6 7 8
1 2 3 4 5 6 7 8
B= 0 3 3
0 1 2 3 4 5
C= 1 2 4 65 7 8
Dr. Sudhir Ranjan Pattanaik
DAA
Radix Sort
National Institute of Science & Technology
Radix Sort takes parameters: the array and the
number of digits in each array element
Radix-Sort(A, d)
1 for i = 1..d
2 do sort the numbers in arrays A by their i-th
digit from the right, using a stable sorting
algorithm
Dr. Sudhir Ranjan Pattanaik
DAA
Radix Sort Example
National Institute of Science & Technology
329 720 720 329
457 355 329 355
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839
Dr. Sudhir Ranjan Pattanaik
DAA
Radix Sort
Correctness and Running Time
National Institute of Science & Technology
•What is the running time of radix sort?
•Each pass over the d digits takes time O(n+k), so total
time O(dn+dk)
•When d is constant and k=O(n), takes O(n)
time
•Stable, Fast
•Doesn’t sort in place (because counting sort is used)
Dr. Sudhir Ranjan Pattanaik
DAA
Bucket Sort
National Institute of Science & Technology
• Assumption: input - n real numbers from [0, 1)
• Basic idea:
– Create n linked lists (buckets) to divide interval [0,1) into
subintervals of size 1/n
– Add each input element to appropriate bucket and sort
buckets with insertion sort
• Uniform input distribution → O(1) bucket size
– Therefore the expected total time is O(n)
Dr. Sudhir Ranjan Pattanaik
DAA
Bucket Sort
National Institute of Science & Technology
Bucket-Sort(A)
1. n length(A)
2. for i 0 to n Distribute elements over buckets
3. do insert A[i] into list B[floor(n*A[i])]
4. for i 0 to n –1 Sort each bucket
5. do Insertion-Sort(B[i])
6. Concatenate lists B[0], B[1], … B[n –1] in
order
Dr. Sudhir Ranjan Pattanaik
DAA
Bucket Sort Example
National Institute of Science & Technology
.78
0 .1
.17 .12 .17
1 .1
2
.39 .21 .23 .26
2 .2
7
.26
3 .39 .2
1
.72
4 .2
3
.94
5 .3
6
.21 .68
6 .6
9
.12 .72 .78
7 .87
.23
8 .27
.68
9 .94 .89
Dr. Sudhir Ranjan Pattanaik
DAA
Bucket Sort – Running Time
National Institute of Science & Technology
• All lines except line 5 (Insertion-Sort) take O(n) in the worst
case.
• In the worst case, O(n) numbers will end up in the same
bucket, so in the worst case, it will take O(n2) time.
• Lemma: Given that the input sequence is drawn uniformly at
random from [0,1), the expected size of a bucket is O(1).
• So, in the average case, only a constant number of elements
will fall in each bucket, so it will take O(n) (see proof in
book).
• Use a different indexing scheme (hashing) to distribute the
numbers uniformly.
Dr. Sudhir Ranjan Pattanaik
DAA
Stable Sorting Algorithms
National Institute of Science & Technology
A sorting algorithms is stable if for any two
indices i and j with i < j and ai = aj, element ai
precedes element aj in the output sequence.
Input
21 71 41 42 22 51 23 61
Output
21 22 23 41 42 51 61 71
Dr. Sudhir Ranjan Pattanaik
DAA
National Institute of Science & Technology
Which sorting algorithms are stable and why?
Dr. Sudhir Ranjan Pattanaik [14]
