Selection Sort and Insertion Sort

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element. The first element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the second element. The first element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the second element. The second element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the third element. The second element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the forth element. The second element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the forth element. The forth element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the fifth element. The forth element is colored in orange.

Determine the lowest value

Selection sort

A schematic representation of a list with unordered numbers. The forth element is colored in orange. There are two arrows that represent that the first and the forth elements will be swapped.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first element is colored in orange. The first and the forth elements have been swapped.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first element is colored in blue and the second element in orange. There is one pointer that points to the second element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first element is colored in blue and the second element in orange. There is one pointer that points to the third element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first element is colored in blue and the second element in orange. There is one pointer that points to the forth element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first element is colored in blue and the second element in orange. There is one pointer that points to the fifth element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue. There is one pointer that points to the third element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue and the third element is colored in orange. There is one pointer that points to the third element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue and the forth element is colored in orange. There is one pointer that points to the forth element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue and the forth element is colored in orange. There are two arrows that represent that the third and forth items will be swapped.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue and the third element is colored in orange. The third and the forth items have been swapped.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in blue. There is one pointer that points to the forth element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in blue, and the forth element is colored in orange. There is one pointer that points to the forth element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in blue, and the fifth element is colored in orange. There is one pointer that points to the fifth element.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in blue, and the fifth element is colored in orange. There are two arrows that represent that the forth and the fifth elements will be swapped.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in blue, and the forth element is colored in orange. The forth and the fifth elements have been swapped.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. The first, second, third, and forth elements are colored in blue.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort

A schematic representation of a list with unordered numbers. All the elements are colored in blue.

Determine the lowest value
Swap the lowest value with the first unordered element

Selection sort - implementation

def selection_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length - 1):

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

Selection sort - complexity

Worst case: $O(n^2)$
Average case: $\Theta(n^2)$
Best case: $\Omega(n^2)$

Insertion sort

A schematic representation of a list with unordered numbers.

Insertion sort

A schematic representation of a list with unordered numbers. The first element is colored in blue and the second element has been elevated above the others.

Insertion sort

A schematic representation of a list with unordered numbers. The first element is colored in blue and the second element has been elevated above the others. The first element has been shifted to the right.

Insertion sort

A schematic representation of a list with unordered numbers. The second element is colored in blue. The element that was elevated is now on the first position.

Insertion sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue.

Insertion sort

A schematic representation of a list with unordered numbers. The first and second elements are colored in blue. The third element has been elevated above the others.

Insertion sort

A schematic representation of a list with unordered numbers. The first, second and third elements are colored in blue.

Insertion sort

A schematic representation of a list with unordered numbers. The first, second and third elements are colored in blue. The third element has been elevated above the others.

Insertion sort

A schematic representation of a list with unordered numbers. The first, second and third elements are colored in blue. The third element has been elevated above the others. The third element has been shifted to the right.

Insertion sort

A schematic representation of a list with unordered numbers. The first, second, third and forth elements are colored in blue.

Insertion sort

A schematic representation of a list with unordered numbers. The first, second, third and forth elements are colored in blue. The fifth element has been elevated above the others.

Insertion sort

A schematic representation of a list with unordered numbers. The first, second, third and forth elements are colored in blue. The fifth element has been elevated above the others. The forth element has been shifted to the right.

Insertion sort

Insertion sort - implementation

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

Insertion sort - complexity

Worst case: $O(n^2)$
Average case: $\Theta(n^2)$
Best case: $\Omega(n)$

Let's practice!

Data Structures and Algorithms in Python