COMP171 Fa2006 Lower bound for sorting radix sort
Lower bound for sorting, radix sort COMP171 Fall 2006
Sorting N/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 2(N log n) comparisons in the worst case(worse-case input) to sort n elements
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 N/Slide 3 Lower bound for sorting Suppose we want to sort n distinct elements How many possible orderings do we have for Elements? We can have N! possible orderings(e.g, the sorted output for a, b, c can be a b c, b a c, acb, c ab, cb a, bca)
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 N/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 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 N/Slide 5 <b< a<c<b Decision tree for b<a<c Algorithm X for sorting b<c<a c<asb three elements a, b, c c<b<a b<a < b a<c<b c<b<a c<a<b b<c c<b a<c c<a b<a<c c<b<a b<c c<asb b<c<a a <c<b a<c c<a <c < b b<a<c a <b<
Sorting IV / Slide 5 Decision tree for Algorithm X for sorting three elements a, b, c