Bubble sort

Algorithm.

```for i = n downto 2 do for j = 1 to i-1 do if A[j] > A[j+1] then A[j] <-> A[j+1]```

Complexity (comparisons). The conditional is executed on every iteration of the inner loop. Therefore, the number of comparisons is the same for all inputs of size $n$.

• $\underset{i=2}{\overset{n}{\Sigma }}\underset{j=1}{\overset{i-1}{\Sigma }}1$
• $=\frac{\left(n-1\right)n}{2}$

Complexity (exchanges). The best case occurs when the list is already sorted. Here, the conditional is never executed and $0$ swaps occur.

The wost case occurs when the list is reversed. Here, the conditional is always true and therefore swaps and comparisons are equivalent: $\frac{\left(n-1\right)n}{2}$.

The average case is more difficult to understand. In a randomly distributed array, the probability that any pair of elements will be transposed is $\frac{1}{2}$. Since every pair of transposed elements requires a swap we take half the total pairs. This is $\frac{1}{2}\left(\genfrac{}{}{0}{}{n}{2}\right)=\frac{\left(n-1\right)n}{4}$.

Insertion sort (with sentinel)

Algorithm.

```A[0] = -inf for i = 2 to n do t = A[i] j = i-1 while t < A[j] do A[j+1] = A[j] j = j-1 A[j+1] = t```

Complexity (comparisons). All comparisons occur in the while loop.

For the best case, the while loop never actually executes, requiring $n-1$ comparisons.

For the worst case, the while loop executes until reaching the sentinel every time (reverse sorted).

• $\underset{i=1}{\overset{n}{\Sigma }}i$
• $=\frac{\left(n-1\right)\left(n+2\right)}{2}$

The average case requires calculating the expected value. The outer summation with index $i$ represents the for loop and the summation with index $j$ calculates the expected value of comparisons for all possible elements $A\left[i\right]$. Since $A\left[i\right]$ is equally likely to land anywhere in the subarray $A\left[1\dots i\right]$, take the expected value over all those possible positions.

• $\underset{i=2}{\overset{n}{\Sigma }}\underset{j=1}{\overset{i}{\Sigma }}\left(\frac{1}{i}\right)\left(i-j+1\right)$
• $=\frac{\left(n-1\right)\left(n+4\right)}{4}$

Complexity (exchanges). For the purposes of this analysis we will also count the sentinel assignment.

For the best case, you only move to the temporary variable $t$ and then move back to the array. This requires $2n-1$ exchanges.

For the worst case, you must move every sorted element. Instead of calculating a summation we can see there’s a relationship between comparisons in the worst case and moves. Inside the for loop we do one more move than comparison.

• $\frac{\left(n-1\right)\left(n+2\right)}{2}+\left(n-1\right)+1$
• $=\frac{\left(n-1\right)\left(n+2\right)}{2}+n$

For the average case, we use apply the same relationship technique.

• $\frac{\left(n-1\right)\left(n+4\right)}{4}+\left(n-1\right)+1$
• $=\frac{\left(n-1\right)\left(n+4\right)}{4}+n$

Insertion sort (without sentinel)

Algorithm.

```for i = 2 to n do t = A[i] j = i-1 while j > 0 and t < A[j] do A[j+1] = A[j] j = j-1 A[j+1] = t```

Complexity (comparisons). All comparisons occur in the while loop. We don’t count the boundary check as an extra comparison even if it would take time in real life.

For the best case, the while loop never actually executes, requiring $n-1$ comparisons.

For the worst case, the while loop executes until reaching the edge of the array every time (reverse sorted).

• $\underset{i=1}{\overset{n}{\Sigma }}\left(i-1\right)$
• $=\frac{\left(n-1\right)n}{2}$

The average case is equiavalent to the non-sentinel version except we do no sentinel comparisons. Therefore, if we can calculate the average number of sentinel comparisons, we have our answer.

• $\underset{i=2}{\overset{n}{\Sigma }}\frac{1}{i}$
• $={H}_{n}-1$

Therefore, the total comparisons is $\frac{\left(n-1\right)\left(n+4\right)}{4}-{H}_{n}+1$.

Complexity (exchanges). This is not affected by the sentinel at all.

Selection sort

Algorithm.

```for i = n downto 2 do k = 1 for j = 2 to i do if A[j] > A[k] then k = j A[k] <-> A[i]```

Complexity (comparisons). The analysis is equivalent for all possible cases. There is a comparison every inner iteration no matter what.

• $\underset{i=2}{\overset{n}{\Sigma }}\underset{j=2}{\overset{i}{\Sigma }}1$
• $=\frac{\left(n-1\right)n}{2}$

Complexity (exchanges). Once again, the anlysis holds for all possible cases. There is an exchange every outer iteration.

• $\underset{i=2}{\overset{n}{\Sigma }}1$
• $=n-1$