Comparison Sorts
- Tags
- comp-sci
A sorting algorithm that relies on [see page 3, comparing] elements with each other.
Note: an algorithm that performs few comparisons could be preferable to ones making many comparisons (such as quick sort) depending on the needs of the problem. Comparisons can be [see page 20, costly], especially if the keys to be compared are not numbers but more complex objects (Strings, Arrays, etc.)
Lower Bound for Comparison Sorts
There is also a lower-bound for the running time of all sorting algorithms that rely on comparisons only.
The proof for this involves [see page 8, imagining] the execution of a comparison-sorting algorithm as a decision tree. The worst case performance of any sorting algorithm based on comparisons equals the length of the longest simple path from the root to any reachable leaf (I.E. the height of the tree). Because a tree with height \( h \) has no more than \( 2^h \) leaves and there're at most \( n! \) factorial leaves in any decision tree (see fig:dec-tree), to accommodate \( n! \) factorial leaves we must satisfy \( 2^h \geq n! \) which is equivalent to \( h \geq \log_2 n! \) which can be [see page 13, shown] to be \( \Omega(n \log n) \). This is the lower bound for any comparison based sorting algorithm.
\begin{figure}
\centering
\begin{tikzpicture}[
every tree node/.style={draw,rectangle},
level distance=1.25cm,sibling distance=.5cm,
edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},
comp/.style={red},
leaf/.style={blue}]
\Tree
[.\node[comp] {$1:2$};
\edge node[auto=right] {\( \leq \)};
[.\node[comp] {$2:3$};
\edge node[auto=right] {\( \leq \)};
[.\node[leaf] {\( \langle 1, 2, 3 \rangle \)};]
\edge node[auto=left] {\( > \)};
[.\node[comp] {$1:3$};
\edge node[auto=right] {\( \leq \)};
[.\node[leaf] {\( \langle 1, 3, 2 \rangle \)};]
\edge node[auto=left] {\( > \)};
[.\node[leaf] {\( \langle 3, 1, 2 \rangle \)};]]]
\edge node[auto=left] {\( > \)};
[.\node[comp] {$1:3$};
\edge node[auto=right] {\( \leq \)};
[.\node[leaf] {\( \langle 2, 1, 3 \rangle \)};]
\edge node[auto=left] {\( > \)};
[.\node[comp] {$2:3$};
\edge node[auto=right] {\( \leq \)};
[.\node[leaf] {\( \langle 2, 3, 1 \rangle \)};]
\edge node[auto=left] {\( > \)};
[.\node[leaf] {\( \langle 3, 2, 1 \rangle \)};]]]]
\end{tikzpicture}
\caption{Decision tree for sorting an array \( [a_1, a_2, a_3] \).
Inner nodes of the form \( i:j \) means comparing element \( i \) with element
\( j \) in the array.
Leaf nodes shows the sorted output for the array such that \( \langle i, j, k \rangle \)
corresponds to a sorted output array of the form \( [a_i, a_j, a_k] \).}
\label{fig:dec-tree}
\end{figure}