Array Sorting - Algorithms Visualized

Array Sorting

Pick a sorting algorithm and watch it rearrange the array one comparison at a time. Selection and insertion sort are simple but take quadratic time. On the other hand, merge sort, quicksort, and heapsort use divide and conquer, randomness, and a heap to reach $O(n \log n)$

Selection Sort¶

Each pass scans the unsorted suffix $A[i..n-1]$ for its minimum and swaps it into position $i$ . The scan always runs to the end, no matter what it finds, so every input costs the same:

Best Case: $\Theta(n^2)$

Average Case: $\Theta(n^2)$

Worst Case: $\Theta(n^2)$

\begin{aligned} C(n) &= \sum_{i=0}^{n-1} (n - 1 - i) \\ &= \sum_{k=0}^{n-1} k \\ &= \frac{n(n-1)}{2} \\ &= O(n^2). \end{aligned}

(1)

Insertion Sort¶

Each pass takes $A[i]$ and shifts it left past every larger element in the sorted prefix $A[0..i-1]$ . Every shift fixes exactly one inversion, a pair $(i, j)$ with $i < j$ and $A[i] > A[j]$ , so the cost depends on how out of order the input is.

Best Case: $\Theta(n)$

In the best case the array is already sorted, so each element is compared once and never moves:

\begin{aligned} C_{\text{best}}(n) &= \sum_{i=1}^{n-1} 1 \\ &= n - 1 \\ &= \Theta(n). \end{aligned}

(2)

Worst Case: $\Theta(n^2)$

In the worst case the array is reversed, so element $i$ is shifted past all $i$ elements before it:

\begin{aligned} C_{\text{worst}}(n) &= \sum_{i=1}^{n-1} i \\ &= \frac{n(n-1)}{2} \\ &= \Theta(n^2). \end{aligned}

(3)

Average Case: $\Theta(n^2)$

On average, each of the $\binom{n}{2}$ pairs is inverted with probability $\frac{1}{2}$ , so the expected number of shifts is

\begin{aligned} \mathbb{E}[I] &= \binom{n}{2} \cdot \frac{1}{2} \\ &= \frac{n(n-1)}{4} \\ &= \Theta(n^2). \end{aligned}

(4)