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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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 forth element.

  • Determine the lowest value
  • Swap the lowest value with the first unordered element
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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 fifth element.

  • Determine the lowest value
  • Swap the lowest value with the first unordered element
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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 fifth element.

  • Determine the lowest value
  • Swap the lowest value with the first unordered element
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

Selection sort - complexity

  • Worst case: $O(n^2)$
  • Average case: $\Theta(n^2)$
  • Best case: $\Omega(n^2)$
Data Structures and Algorithms in Python

Insertion sort

A schematic representation of a list with unordered numbers.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

Insertion sort

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

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

Insertion sort

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

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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 and second elements have been shifted to the right.

Data Structures and Algorithms in Python

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, second, and third elements have been shifted to the right.

Data Structures and Algorithms in Python

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, second, and third elements have been shifted to the right. The element that was elevated is now on the first position.

Data Structures and Algorithms in Python

Insertion sort

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

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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 element that was elevated is now on the forth position.

Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

Insertion sort - complexity

  • Worst case: $O(n^2)$
  • Average case: $\Theta(n^2)$
  • Best case: $\Omega(n)$
Data Structures and Algorithms in Python

Let's practice!

Data Structures and Algorithms in Python

Preparing Video For Download...