This chapter provides knowledge of sorting lower bound. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Sorting Lower Bound 3/29/14 21:28 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Sorting Lower Bound © 2014 Goodrich, Tamassia, Goldwasser Sorting Lower Bound 1 Comparison-Based Sorting ! Many sorting algorithms are comparison based. n n They sort by making comparisons between pairs of objects Examples: bubble-sort, selection-sort, insertion-sort, heap-sort, merge-sort, quick-sort, . ! Let us therefore derive a lower bound on the running time of any algorithm that uses comparisons to sort n elements, x1, x2, , xn. Is xi < xj? no yes © 2014 Goodrich, Tamassia, Goldwasser Sorting Lower Bound 2 1 Sorting Lower Bound 3/29/14 21:28 Counting Comparisons ! Let us just count comparisons then. ! Each possible run of the algorithm corresponds to a root-to-leaf path in a decision tree xi < xj ? xa < xb ? xe < xf ? © 2014 Goodrich, Tamassia, Goldwasser xc < xd ? x m < xo ? xk < xl ? xp < xq ? Sorting Lower Bound 3 Decision Tree Height ! The height of the decision tree is a lower bound on the running time ! Every input permutation must lead to a separate leaf output ! If not, some input 4 5 would have same output ordering as 5 4 , which would be wrong ! Since there are n!=1⋅2 ⋅ ⋅n leaves, the height is at least log (n!) minimum height (time) xi < x j ? xa < xb ? xc < xd ? log (n!) xe < xf ? © 2014 Goodrich, Tamassia, Goldwasser xk < xl ? n! Sorting Lower Bound xm < xo ? xp < xq ? 4 2 Sorting Lower Bound 3/29/14 21:28 The Lower Bound ! Any comparison-based sorting algorithms takes at least log (n!) time ! Therefore, any such algorithm takes time at least n 2 ⎛ n ⎞ log (n!) ≥ log ⎜ ⎟ = (n / 2) log (n / 2). ⎝ 2 ⎠ ! That is, any comparison-based sorting algorithm must run in Ω(n log n) time. © 2014 Goodrich, Tamassia, Goldwasser Sorting Lower .
