Sorting in O(N) time

CS202
Data Structures & Algorithms

1
 How Fast Can We Sort?

• Selection Sort, Bubble Sort, Insertion Sort: O(n2)

• Heap Sort, Merge sort: O(nlgn)

• Quicksort: O(nlgn) - average

• What is common to all these algorithms?

– Make comparisons between input elements

ai < aj, ai ≤ aj, ai = aj, ai ≥ aj, or ai > aj

2
 Can we do better?

• Linear sorting algorithms

– Counting Sort

– Radix Sort

– Bucket sort

• Make certain assumptions about the data

• Linear sorts are NOT “comparison sorts”

3
 Counting Sort
• Assumptions:
– n integers which are in the range [0 ... r]
– r is in the order of n, that is, r=O(n)
• Idea:
– For each element x, find the number of elements  x
– Place x into its correct position in the output array

output array

4
Step 1

(i.e., frequencies)

(r=6)

5
 Step 2

C (frequencies) Cnew (cumulative sums)

6
 Algorithm

• Start from the last element of A

• Place A[i] at its correct place in the output array

• Decrease C[A[i]] by one

1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3
0 1 2 3 4 5

Cnew 2 2 4 7 7 8
7
 Example
1 2 3 4 5 6 7 8 0 1 2 3 4 5

A 2 5 3 0 2 3 0 3 Cnew 2 2 4 7 7 8

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

B 3 B 0 3
0 1 2 3 4 5
0 1 2 3 4 5

Cnew 2 2 4 6 7 8 Cnew 1 2 4 6 7 8

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

B 0 3 3 B 0 2 3 3
0 1 2 3 4 5
0 1 2 3 4 5

Cnew 1 2 4 5 7 8 Cnew 1 2 3 5 7 8
8
 Example (cont.)
1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3

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

B 0 0 2 3 3 B 0 0 2 3 3 3 5
0 1 2 3 4 5 0 1 2 3 4 5

C 0 2 3 5 7 8 C 0 2 3 4 7 7

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

B 0 0 2 3 3 3 B 0 0 2 2 3 3 3 5
0 1 2 3 4 5

C 0 2 3 4 7 8

9
 COUNTING-SORT
1 j n

A
Alg.: COUNTING-SORT(A, B, n, k) 0 k

1. for i ← 0 to r C
2. do C[ i ] ← 0 B
1 n

3. for j ← 1 to n
4. do C[A[ j ]] ← C[A[ j ]] + 1
5. C[i] contains the number of elements equal to i
6. for i ← 1 to r
7. do C[ i ] ← C[ i ] + C[i -1]
8. C[i] contains the number of elements ≤ i
9. for j ← n downto 1
10. do B[C[A[ j ]]] ← A[ j ]
11. C[A[ j ]] ← C[A[ j ]] - 1
10
 Analysis of Counting Sort
Alg.: COUNTING-SORT(A, B, n, k)
1. for i ← 0 to r O(r)
2. do C[ i ] ← 0
3. for j ← 1 to n
O(n)
4. do C[A[ j ]] ← C[A[ j ]] + 1
5. C[i] contains the number of elements equal to i
6. for i ← 1 to r
O(r)
7. do C[ i ] ← C[ i ] + C[i -1]
8. C[i] contains the number of elements ≤ i
9. for j ← n downto 1
10. do B[C[A[ j ]]] ← A[ j ] O(n)

11. C[A[ j ]] ← C[A[ j ]] - 1

Overall time: O(n + r) 11
 Analysis of Counting Sort
• Overall time: O(n + r)

• In practice we use COUNTING sort

when r = O(n)

 running time is O(n)

12
 Radix Sort
• Represents keys as d-digit numbers in some
base-k
key = x1x2...xd where 0≤xi≤k-1

• Example: key=15

key10 = 15, d=2, k=10 where 0≤xi≤9

key2 = 1111, d=4, k=2 where 0≤xi≤1

13
 Radix Sort
• Assumptions
d=O(1) and k =O(n)
• Sorting looks at one column at a time
– For a d digit number, sort the least significant
digit first
– Continue sorting on the next least significant
digit, until all digits have been sorted
– Requires only d passes through the list

14
 RADIX-SORT
Alg.: RADIX-SORT(A, d)
for i ← 1 to d
do use a stable sort to sort array A on digit i
(stable sort: preserves order of identical elements)

15
 Analysis of Radix Sort

• Given n numbers of d digits each, where each

digit may take up to k possible values, RADIX-

SORT correctly sorts the numbers in O(d(n+k))

– One pass of sorting per digit takes O(n+k) assuming

that we use counting sort

– There are d passes (for each digit)

16
 Analysis of Radix Sort

• Given n numbers of d digits each, where each

digit may take up to k possible values, RADIX-

SORT correctly sorts the numbers in O(d(n+k))

– Assuming d=O(1) and k=O(n), running time is O(n)

17
 Bucket Sort
• Assumption:
– the input is generated by a random process that distributes
elements uniformly over [0, 1)
• Idea:
– Divide [0, 1) into k equal-sized buckets (k=Θ(n))
– Distribute the n input values into the buckets
– Sort each bucket (e.g., using quicksort)
– Go through the buckets in order, listing elements in each one

• Input: A[1 . . n], where 0 ≤ A[i] < 1 for all i

• Output: elements A[i] sorted

18
 Example - Bucket Sort
A 1 .78 B 0 /

2 .17 1 .17 .12 /

3 .39 2 .26 .21 .23 /

4 .26 3 .39 /

5 .72 4 / Distribute
6 .94 5 / Into buckets
7 .21 6 .68 /

8 .12 7 .78 .72 /

9 .23 8 /
10 .68 9 .94 /
19
 Example - Bucket Sort

0 /

1 .12 .17 /

2 .21 .23 .26 /

3 .39 /
Sort within each
4 /
bucket
5 /

6 .68 /

7 .72 .78 /

8 /

9 .94 / 20
 Example - Bucket Sort
.12 .17 .21 .23 .26 .39 .68 .72 .78 .94 /

0 /

1 .12 .17 /

2 .21 .23 .26 /

3 .39 /

4 /

5 / Concatenate the lists from

6 .68 / 0 to n – 1 together, in order

7 .72 .78 /

8 /

9 .94 / 21
 Analysis of Bucket Sort
Alg.: BUCKET-SORT(A, n)

for i ← 1 to n
O(n)
do insert A[i] into list B[nA[i]]

for i ← 0 to k - 1
k O(n/k log(n/k))
do sort list B[i] with quicksort sort =O(nlog(n/k)

concatenate lists B[0], B[1], . . . , B[n -1]

O(k)
together in order

return the concatenated lists

O(n) (if k=Θ(n))
22