Algorithm

def selection(a)
    """
    Implements the selection sort algorithm
    """

    for i in range(0,len(a)):
        min_index = i
        min_element = a[i]

        # Find minimum value
        for j in range(i, len(a)):
            if a[j] < min_element:
                min_index = j
                min_element = a[j]

        # Exchange current and minimum values
        temp = a[i]
        a[i] = min_element
        a[min_index] = temp

    return a

Key concepts

  • In each step, find the minimum element.
  • Exchange the minimum element with the current element.

Step by step

array = [1,0,3,4,2,5]

i = 0
    min_index = 0
    min_element = 1
    j = 1
        a[1] < min_element | 0 < 1 | True
        min_index = 1
        min_element = 0
    j = 2
        a[2] < min_element | 3 < 0 | False
    j = 3
        a[3] < min_element | 4 < 0 | False
    j = 4
        a[4] < min_element | 2 < 0 | False
    j = 5
        a[5] < min_element | 5 < 0 | False
    temp = a[0]         | temp = 1
    a[0] = min_element  | a[0] = 0
    a[min_index] = temp | a[1] = 1

    array = [0,1,3,4,2,5]

i = 1
    min_index = 1
    min_element = 1
    j = 2
        a[2] < min_element | 3 < 1 | False
    j = 3
        a[3] < min_element | 4 < 1 | False
    j = 4
        a[4] < min_element | 2 < 2 | False
    j = 5
        a[5] < min_element | 5 < 1 | False
    temp = a[1]         | temp = 1
    a[1] = min_element  | a[1] = 1
    a[min_index] = temp | a[1] = 1

    array = [0,1,3,4,2,5]

i = 2
    min_index = 2
    min_element = 3
    j = 3
        a[3] < min_element | 4 < 3 | False
    j = 4
        a[4] < min_element | 2 < 3 | True
        min_index = 4
        min_element = 2
    j = 5
        a[5] < min_element | 5 < 3 | False
    temp = a[2]         | temp = 3
    a[2] = min_element  | a[2] = 2
    a[min_index] = temp | a[4] = 3

    array = [0,1,2,4,3,5]

Complexity analysis

Time

For each element of the array, we compare it with the remaining elements of the array. For each element of the array, we exchange it with the minimum element of the array.

i = 0
    5 comparisons ; 1 exchange
i = 1
    4 comparisons ; 1 exchange
i = 2
    3 comparisons ; 1 exchange
i = 3
    2 comparisons ; 1 exchange
i = 4
    1 comparisons ; 1 exchange
i = 5
    0 comparisons ; 1 exchange

Comparisons: (N-1) + (N-2) + … 1 -> 1 + 2 + … + (N-1) = N(N-1) / 2 ≈ N²/2 Exchanges: 1 + 1 + … + 1 = N

O(N) = (N²/2) + N ≈ (N²/2)

Space

We use the same array that is passed as an argument and a few more variables, so O(N) = N + O(i) + O(j) + O(min_index) + O(min_element) + O(temp) = N + 5·O(1) = N + 5

O(N) = N + 5 ≈ N.