CSCE 411 Lecture 2

Lecture Slides

« previous | Wednesday, August 29, 2012 | next »

Sorting Algorithms

Donald Knuth, The Art of Computer Programming, Vol. 3 is dedicated to sorting algorithms.

Incrementally build up longer and longer prefixes of the array of keys that is in sorted order by taking the "current" key, and inserting it at its correct position

Comparison-based sorting algorithms run in best-case Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log{n})}

Proof of n log n Lower Bound

• consider any comparison-based sorting algorithm
• represent behavior with decision tree
• node corresponds to execution of comparison (has two children depending on whether result is true or false)
• leaf represents correct sorted order for that path

a.size == n == 3

a[1] <= a[2] ?
|-- YES: a[2] <= a[3] ?
|   |-- YES: [ a[1], a[2], a[3] ]
|   |
|   `-- NO: a[1] <= a[3] ?
|       |-- YES: [ a[1], a[3], a[2] ]
|       `-- NO: [ a[3], a[1], a[2] ]
`-- NO: a[1] <= a[3] ?
    |-- YES: [ a[2], a[1], a[3] ]
    `-- NO: a[2] <= a[3] ?
        |-- YES: [ a[2], a[3], a[1] ]
        `-- NO: [ a[3], a[2], a[1] ]

Number of leaves = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!} because there must be one leaf for every permutation of input

Each node has only two children, so the height of a binary tree with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!} leaves is $\Omega (n\log {n})$

Proof. A full binary tree of height Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} has at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^h} leaves, so

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 2^h &\ge n! \\ \log_2\left(2^h\right) & \ge \log_2(n!) = \log_2(n(n-1)\dots(2)(1)) \\ h &\ge \log_2(n!) \ge \log_2\left(n^n\right) & (n! \in \Omega(n^n)) \\ h &\ge n \log_2{n} \\ h &\in \Omega(n \log{n}) \end{align}}

Therefore, all comparison-based sorting algorithms have a worst-case running time of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(n \log{n})} in their decision tree.