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 $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 = $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 $n!$ leaves is $\Omega (n\log {n})$

Proof. A full binary tree of height $h$ has at most $2^{h}$ leaves, so

${\begin{aligned}2^{h}&\geq n!\\\log _{2}\left(2^{h}\right)&\geq \log _{2}(n!)=\log _{2}(n(n-1)\dots (2)(1))\\h&\geq \log _{2}(n!)\geq \log _{2}\left(n^{n}\right)&(n!\in \Omega (n^{n}))\\h&\geq n\log _{2}{n}\\h&\in \Omega (n\log {n})\end{aligned}}$

Therefore, all comparison-based sorting algorithms have a worst-case running time of $\Omega (n\log {n})$ in their decision tree.