#complexity analysis

Example

A bold element is the minimum element found in the specific iteration and that should be swapped. Underlined elements are those that we consider sorted, e.g. in correct order, and don't need to be compared again.

Let's sort the following list $$ A = [16, 4, 9, 3, 15, 5, 7] $$

[16, 4, 9, 3, 15, 5, 7]

[3, 4, 9, 16, 15, 5, 7]

[3, 4, 9, 16, 15, 5, 7]

[3, 4, 5, 16, 15, 9, 7]

[3, 4, 5, 7, 15, 9, 16]

[3, 4, 5, 7, 9, 15, 16]

[3, 4, 5, 7, 9, 15, 16]

[3, 4, 5, 7, 9, 15, 16]

And sorted! Number comparisons in total needed: $ 21 $.

Implementation in Python

a = [16, 4, 9, 3, 15, 5, 7] for i in range(0, len(a) - 1): for j in range(i + 1, len(a)): if a[j] < a[min]: min = j temp = a[min a[min] = a[i] a[i] = temp

Complexity analysis

The complexity analysis for selection sort is pretty much the same as for bubble sort. Note that, for explanations about the math parts see my explanations for Bubble sort. They are the same here.

Just like for bubble sort, we start translating our for loops into sums, and let $ c(n) $ be our function to count how many times the critical operation executes.

$$ c(n) = \sum_{i = 0}^{n-2} \sum_{j = i + 1}^{n - 1} 1 = \sum_{i = 0}^{n-2} (n - 1 - i) = \frac{n(n-1)}{2}. $$

Hence, $ c(n) \in \Theta(n^2) $.

Example

An unsorted list with 5 elements, i.e. $ n = 5 $: $ A = [3, 5, 2, 1, 6] $

Underlined elements are in the correct order. Bold elements are those being compared.

$i = 0:$ [3, 5, 2, 1, 6] is $ 3 > 5 $? No, move on.

[3, 5, 2, 1, 6] is $ 5 > 2 $? Yes, swap.

[3, 2, 5, 1, 6] is $ 5 > 1 $? Yes, swap.

[3, 2, 1, 5, 6] is $ 5 > 6 $? No, move on.

$ i = 1: $ [3, 2, 1, 5, 6] is $ 3 > 2 $? Yes, swap.

[2, 3, 1, 5, 6] is $ 3 > 1 $? Yes, swap.

[2, 1, 3, 5, 6] is $ 3 > 5 $? No, move on.

$ i = 2: $ [2, 1, 3, 5, 6] is $ 2 > 1 $? Yes, swap.

[1, 2, 3, 5, 6] is $ 2 > 3 $? No, move on.

$ i = 3: $ [1, 2, 3, 5, 6] is $ 1 > 2$? No, move on.

At this step, the whole array is assumed to be sorted and we're done.

Implementation in Python

a = [3, 5, 2, 1, 6] for i in range(len(a)-1): for j in range(len(a) - 1 - i): // If two adjacent elements are in wrong order, swap them if a[j] > a[j+1]: temp = a[j] a[j] = a[j+1] a[j+1] = temp print(a);

Complexity analysis

This sorting algorithm is pretty slow, but let's see how slow.

As usual we start by writing the sums (they are easily translated from the for loops). Let $ c(n) $ be the function that yields how many times the most critical operation executes in the algorithm (in bubble sort it's obvious, the compare operation). We get

$$ c(n) = \sum_{i = 0}^{n-2} \sum_{j = 0}^{n - 2 - i} 1 $$

Since $$ \sum_{j = 0}^{n - 2 - i} 1 = (n - 2 - i) - 0 + 1 = n - 1 - i $$

we rewrite the sum to

$$ c(n) = \sum_{i = 0}^{n-2}(n - 1 - i). $$

If we would expand this sum it would look like this $$ (n - 1 - 0) + (n - 1 - 1) + (n - 1 - 2) + .. + 0 $$ i.e. $$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (n - 1) $$

and this sequence has a known formula:

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (n - 1) = \frac{n(n-1)}{2}. $$

To summarize, we now have that

$$ c(n) = \sum_{i = 0}^{n-2} \sum_{j = 0}^{n - 2 - i} 1 = \frac{n(n-1)}{2} $$

which means that $ c(n) \in \Theta(n^2) $.

Also, recall that in the example above we saw that the critical operation executed $ 10 $ times for $ n = 5 $ elements. That's reasonable because

$$ \frac{n(n-1)}{2} = \frac{5 \cdot (5 - 1)}{2} = 10. $$

Extra: Proof

Let's prove that

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (n - 1) = \frac{n(n-1)}{2} $$

with mathematical induction.

In all steps, left-hand side (LHS) and right-hand side (RHS) should be equal.

Base case $ n = 2$:

$ LHS = (n - 1) = 2 - 1 = 1 $

$ RHS = \frac{n^2-n}{2} = \frac{2^2-2}{2} = 1 $

$ LHS = RHS $.

Induction step: Assume the statement is true for $ n = k $, e.g.

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (k - 1) = \frac{k(k-1)}{2} $$

Then it should hold true for $ n = k + 1 $, e.g.

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (k - 1) + k = \frac{(k+1)((k+1)-1)}{2} = \frac{k(k+1)}{2} $$

Since we assumed that $ 0 + 1 + 2 + 3 + 4 + 5 + .. + (k - 1) = \frac{k(k-1)}{2} $

then it must also hold true that

$$ \frac{k(k-1)}{2} + k = \frac{k(k+1)}{2} $$

Simplify $ LHS $

$$ LHS = \frac{k(k-1)}{2} + k = \frac{k^2-k}{2} + \frac{2k}{2} = \frac{k(k+1)}{2} $$

$ LHS = RHS $.