Lower bound for sorting, radix sort

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

Sorting N/Slide 6 Lower Bound for Sorting a different algorithm would have a different decision tree Decision tree for insertion sort on 3 elements al: a2 a2:a3 al: a3 (al,a2,a3) al: a3 (a2, a1, a3) a2: a (al,a3,a2) (a3,al,a2) (a2, a3, al (a3,a2,al) 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 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 N/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! eaves 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 I log2 (N )I comparisons in the worst case

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 2 d 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 N/Slide 8 Lower Bound for Sorting log2(N])=log(N(N-1)(N-2)…(2)(1) logN+log(N-1)+log(N一2)+…+log2+log1 log N +log(N-1)+log(N-2)+ .+log(N/2) N log w g &(Nlog N) Any sorting algorithm based on comparisons between elements requires Q2(N log N comparisons

Sorting IV / Slide 8 Lower Bound for Sorting Any sorting algorithm based on comparisons between elements requires (N log N) comparisons

Sorting N/Slide 9 Linear time sorting Can we do better(inear 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 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 N /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 toO O(M) Scan through the input list A[, insert A[] into B[AQI= O(N) Scan B once, read out the nonzero integers= O(M) otal 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 19 526 3 11235689 Output: 123568 9

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 5 8 9 Output: 1 2 3 5 6 8 9 3 6