Video 17: Countingsort and Radixsort COMS10017 – (Object-Oriented Programming and) Algorithms
Video 17: Countingsort and Radixsort 1 / 8
Countingsort: Sorting Integers fast
Copyright By PowCoder代写 加微信 powcoder
Countingsort
Input: Integer array A ∈ {0, 1, 2, . . . , k}n, for some integer k Idea
For each element x ∈ {0,1,…,k}, count # elements ≤ x Put elements A[i] directly into correct position
Difficulty: Multiple elements have the same value
Video 17: Countingsort and Radixsort 2 / 8
Require: Array A of n integers from {0, 1, 2, . . . , k }, for some integer k Let C[0…k] be a new array with all entries equal to 0
Store output in array B[0…n − 1]
for i = 0,…,n − 1 do {Count how often each element appears} C[A[i]] ← C[A[i]] + 1
for i = 1, . . . , k do {Count how many smaller (or equal) elements appear} C[i] ← C[i]+C[i −1]
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Last loop processes A from right to left
C[A[i]]: Number of elements smaller or equal to A[i]
Decrementing C[A[i]]: Next element of value A[i] should be left of the current one
Video 17: Countingsort and Radixsort 3 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Counting Sort: Example
Example: n=8,k=5 01234567
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 4 / 8
Analysis: Counting Sort
O(n) + O(k) + O(n) = O(n + k) Counting Sort has runtime O(n)
if k = O(n)
This beats the lower bound
for comparison-based sorting
Stable? In-place? Yes, it is stable (important!) No, not in-place
Correctness Loop Invariant
for i = 0, . . . , n − 1 do C[A[i]] ← C[A[i]] + 1
for i = 1, . . . , k do
C[i] ← C[i]+C[i −1]
for i = n − 1, . . . , 0 do B[C[A[i]] − 1] ← A[i] C[A[i]] ← C[A[i]] − 1
Video 17: Countingsort and Radixsort 5 / 8
Radix Sort
Radix Sort
Input is an array A of d digits integers, each digit is from the set {0, 1, . . . , b − 1}
b = 2, d = 5. E.g. 01101 (binary numbers) b = 10, d = 4. E.g. 9714
Iterate through the d digits
Sort according to the current digit
Video 17: Countingsort and Radixsort
Radix Sort (2)
Radix Sort Algorithm
for i = 1, . . . , d do
Use a stable sort algorithm to sort array A on digit i
(least significant digit is
720 329 329 355 436 436 839 → 457
355 457 657
657 720 839
Video 17: Countingsort and Radixsort 7 / 8
Radix Sort (3)
Given n d-digit number in which each digit can take on up to b possible values. Radix-sort correctly sorts these numbers in O(d(n + b)) time if the stable sort (e.g. Countingsort) it uses takes O(n + b) time.
Proof Runtime is obvious. Correctness follows by induction on the columns being sorted.
Observe: If d = O(1) and b = O(n) then the runtime is O(n)!
Video 17: Countingsort and Radixsort 8 / 8
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com