Selection sort en insertion sort

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het eerste element.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het eerste element. Het eerste element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het tweede element. Het eerste element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het tweede element. Het tweede element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het derde element. Het tweede element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het vierde element. Het tweede element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het vierde element. Het vierde element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Er wijst een pointer naar het vijfde element. Het vierde element is oranje.

Bepaal de kleinste waarde

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het vierde element is oranje. Twee pijlen geven aan dat het eerste en vierde element worden verwisseld.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is oranje. Het eerste en vierde element zijn verwisseld.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw en het tweede oranje. Er wijst een pointer naar het tweede element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw en het tweede oranje. Er wijst een pointer naar het derde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw en het tweede oranje. Er wijst een pointer naar het vierde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw en het tweede oranje. Er wijst een pointer naar het vijfde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw. Er wijst een pointer naar het derde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw en het derde is oranje. Er wijst een pointer naar het derde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw en het derde is oranje. Er wijst een pointer naar het vierde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw en het vierde is oranje. Er wijst een pointer naar het vierde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw en het vierde is oranje. Er wijst een pointer naar het vijfde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw en het vierde is oranje. Twee pijlen geven aan dat het derde en vierde element worden verwisseld.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw en het derde is oranje. Het derde en vierde element zijn verwisseld.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw. Er wijst een pointer naar het vierde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw, en het vierde is oranje. Er wijst een pointer naar het vierde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw, en het vierde is oranje. Er wijst een pointer naar het vijfde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw, en het vijfde is oranje. Er wijst een pointer naar het vijfde element.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw, en het vijfde is oranje. Twee pijlen geven aan dat het vierde en vijfde element worden verwisseld.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw, en het vierde is oranje. Het vierde en vijfde element zijn verwisseld.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn blauw.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort

Een schematische weergave van een lijst met ongesorteerde getallen. Alle elementen zijn blauw.

Bepaal de kleinste waarde
Verwissel die met het eerste ongesorteerde element

Selection sort - implementatie

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 - complexiteit

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

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw en het tweede is boven de anderen geheven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw en het tweede is boven de anderen geheven. Het eerste element is naar rechts verschoven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het tweede element is blauw. Het eerder geheven element staat nu op de eerste positie.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste en tweede element zijn blauw. Het derde element is boven de anderen geheven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw. Het derde element is boven de anderen geheven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw. Het derde element is boven de anderen geheven. Het derde element is naar rechts verschoven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw. Het derde element is boven de anderen geheven. Het derde en tweede element zijn naar rechts verschoven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn blauw. Het derde element is boven de anderen geheven. Het derde, tweede en derde element zijn naar rechts verschoven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn blauw.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn blauw. Het vijfde element is boven de anderen geheven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn blauw. Het vijfde element is boven de anderen geheven. Het vierde element is naar rechts verschoven.

Insertion sort

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn blauw. Het vijfde element is boven de anderen geheven. Het eerder geheven element staat nu op de vierde positie.

Insertion sort - implementatie

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 - complexiteit

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

Laten we oefenen!

Datastructuren en algoritmen in Python