COMP171
Fall 2006
Lower bound for sorting,
radix sort
Sorting IV / Slide 2
Lower Bound for Sorting
☛ Mergesort and heapsort
■ worst-case running time is O(N log N)
☛ Are there better algorithms?
☛ Goal: Prove that any sorting algorithm based
on only comparisons takes Ω(N log N)
comparisons in the worst case (worse-case
input) to sort N elements.
Sorting IV / Slide 3
Lower Bound for Sorting
☛ Suppose we want to sort N distinct elements
☛ How many possible orderings do we have for
N elements?
☛ We can have N! possible orderings (e.g., the
sorted output for a,b,c can be a b c, b a c,
a c b, c a b, c b a, b c a.)
Sorting IV / Slide 4
Lower Bound for Sorting
☛ Any comparison-based sorting process can
be represented as a binary decision tree.
■ Each node represents a set of possible orderings,
consistent with all the comparisons that have been
made
■ The tree edges are results of the comparisons
Sorting IV / Slide 5
Decision tree for
Algorithm X for sorting
three elements a, b, c
Sorting IV / Slide 6
Lower Bound for Sorting
☛ A different algorithm would have a different decision tree
☛ Decision tree for Insertion Sort on 3 elements:
There exists an input ordering that corresponds to each root-to-leaf path to arrive at a
sorted order. For decision tree of insertion sort, the longest path is O(N2).
Sorting IV / Slide 7
Lower Bound for Sorting
☛ The worst-case number of comparisons used by the
sorting algorithm is equal to the depth of the deepest
leaf
■ The average number of comparisons used is equal to the
average depth of the leaves
☛ A decision tree to sort N elements must have N!
leaves
■ a binary tree of depth d has at most 2d leaves
⇒ a binary tree with 2d leaves must have depth at least d
⇒ the decision tree with N! leaves must have depth at least
log2 (N!)
☛ Therefore, any sorting algorithm based on only
comparisons between elements requires at least
log2(N!) comparisons in the worst case.
Sorting IV / Slide 8
Lower Bound for Sorting
☛ Any sorting algorithm based on comparisons
between elements requires Ω(N log N)
comparisons.
Sorting IV / Slide 9
Linear time sorting
☛ Can we do better (linear time algorithm) if the
input has special structure (e.g., uniformly
distributed, every number can be represented
by d digits)? Yes.
☛ Counting sort, radix sort
Sorting IV / Slide 10
Counting Sort
☛ Assume N integers are to be sorted, each is in the range 1 to M.
☛ Define an array B[1..M], initialize all to 0 ⇒ O(M)
☛ Scan through the input list A[i], insert A[i] into B[A[i]] ⇒ O(N)
☛ Scan B once, read out the nonzero integers ⇒ O(M)
Total time: O(M + N)
■ if M is O(N), then total time is O(N)
■ Can be bad if range is very big, e.g. M=O(N2)
N=7, M = 9,
Want to sort 8 1 9 5 2 6 3
1 2 3 5 6 8 9
Output: 1 2 3 5 6 8 9
Sorting IV / Slide 11
Counting sort
☛ What if we have duplicates?
☛ B is an array of pointers.
☛ Each position in the array has 2 pointers:
head and tail. Tail points to the end of a linked
list, and head points to the beginning.
☛ A[j] is inserted at the end of the list B[A[j]]
☛ Again, Array B is sequentially traversed and
each nonempty list is printed out.
☛ Time: O(M + N)
Sorting IV / Slide 12
Counting sort
M = 9,
Wish to sort 8 5 1 5 9 5 6 2 7
1 2 5 6 7 8 9
Output: 1 2 5 5 5 6 7 8 9
Sorting IV / Slide 13
Radix Sort
☛ Extra information: every integer can be
represented by at most k digits
■ d1d2…dk where di are digits in base r
■ d1: most significant digit
■ dk: least significant digit
Sorting IV / Slide 14
Radix Sort
☛ Algorithm
■ sort by the least significant digit first (counting sort)
=> Numbers with the same digit go to same bin
■ reorder all the numbers: the numbers in bin 0
precede the numbers in bin 1, which precede the
numbers in bin 2, and so on
■ sort by the next least significant digit
■ continue this process until the numbers have been
sorted on all k digits
Sorting IV / Slide 15
Radix Sort
☛ Least-significant-digit-first
Example: 275, 087, 426, 061, 509, 170, 677, 503
170 061 503 275 426 087 677 509
Sorting IV / Slide 16
170 061 503 275 426 087 677 509
503 509 426 061 170 275 677 087
061 087 170 275 426 503 509 677
Sorting IV / Slide 17
Radix Sort
☛ Does it work?
☛ Clearly, if the most significant digit of a and b
are different and a < b, then finally a comes
before b
☛ If the most significant digit of a and b are the
same, and the second most significant digit of
b is less than that of a, then b comes before a.
Sorting IV / Slide 18
Radix Sort
Example 2: sorting cards
■ 2 digits for each card: d1d2
■ d1 = ♠♥♣♦: base 4
♦≤♣≤♥≤♠
■ d2 = A, 2, 3, ...J, Q, K: base 13
A ≤ 2 ≤ 3 ≤ ... ≤ J ≤ Q ≤ K
■ ♦2 ≤ ♣2 ≤ ♥5 ≤ ♠K
Sorting IV / Slide 19
A=input array, n=|numbers to be sorted|,
d=# of digits, k=the digit being sorted, j=array index
// base 10
// FIFO
// d times of counting sort
// scan A[i], put into correct slot
// re-order back to original array
Sorting IV / Slide 20
Radix Sort
☛ Increasing the base r decreases the number of
passes
☛ Running time
■ k passes over the numbers (i.e. k counting sorts, with range
being 0..r)
■ each pass takes 2N
■ total: O(2Nk)=O(Nk)
■ r and k are constants: O(N)
☛ Note:
■ radix sort is not based on comparisons; the values are used
as array indices
■ If all N input values are distinct, then k = Ω(log N) (e.g., in
binary digits, to represent 8 different numbers, we need at
least 3 digits). Thus the running time of Radix Sort also
become Ω(N log N).
