Selection sort och insertion sort

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det första elementet.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det första elementet. Det första elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det andra elementet. Det första elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det andra elementet. Det andra elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det tredje elementet. Det andra elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det fjärde elementet. Det andra elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det fjärde elementet. Det fjärde elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det finns en pekare som pekar på det femte elementet. Det fjärde elementet är färgat orange.

  • Hitta det lägsta värdet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det fjärde elementet är färgat orange. Det finns två pilar som visar att det första och det fjärde elementet kommer att byta plats.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat orange. Det första och det fjärde elementet har bytts.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat blått och det andra elementet är färgat orange. Det finns en pekare som pekar på det andra elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat blått och det andra elementet är färgat orange. Det finns en pekare som pekar på det tredje elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat blått och det andra elementet är färgat orange. Det finns en pekare som pekar på det fjärde elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat blått och det andra elementet är färgat orange. Det finns en pekare som pekar på det femte elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå. Det finns en pekare som pekar på det tredje elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå och det tredje elementet är färgat orange. Det finns en pekare som pekar på det tredje elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå och det tredje elementet är färgat orange. Det finns en pekare som pekar på det fjärde elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå och det fjärde elementet är färgat orange. Det finns en pekare som pekar på det fjärde elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå och det fjärde elementet är färgat orange. Det finns en pekare som pekar på det femte elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå och det fjärde elementet är färgat orange. Det finns två pilar som visar att det tredje och fjärde elementet kommer att byta plats.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå och det tredje elementet är färgat orange. Det tredje och fjärde elementet har bytts.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå. Det finns en pekare som pekar på det fjärde elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå och det fjärde elementet är färgat orange. Det finns en pekare som pekar på det fjärde elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå och det fjärde elementet är färgat orange. Det finns en pekare som pekar på det femte elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå och det femte elementet är färgat orange. Det finns en pekare som pekar på det femte elementet.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå och det femte elementet är färgat orange. Det finns två pilar som visar att det fjärde och femte elementet kommer att byta plats.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå och det fjärde elementet är färgat orange. Det fjärde och femte elementet har bytts.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Det första, andra, tredje och fjärde elementet är färgade blå.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i Python

Selection sort

En schematisk representation av en lista med osorterade tal. Alla element är färgade blå.

  • Hitta det lägsta värdet
  • Byt plats på det lägsta värdet och det första osorterade elementet
Datastrukturer och algoritmer i 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
Datastrukturer och algoritmer i Python

Selection sort – komplexitet

  • Värsta fall: $O(n^2)$
  • Genomsnittligt fall: $\Theta(n^2)$
  • Bästa fall: $\Omega(n^2)$
Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat blått och det andra elementet har lyfts upp ovanför de övriga.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första elementet är färgat blått och det andra elementet har lyfts upp ovanför de övriga. Det första elementet har förflyttats åt höger.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det andra elementet är färgat blått. Elementet som lyftes upp befinner sig nu på första positionen.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första och andra elementet är färgade blå. Det tredje elementet har lyfts upp ovanför de övriga.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå. Det tredje elementet har lyfts upp ovanför de övriga.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå. Det tredje elementet har lyfts upp ovanför de övriga. Det tredje elementet har förflyttats åt höger.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå. Det tredje elementet har lyfts upp ovanför de övriga. Det tredje och andra elementet har förflyttats åt höger.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå. Det tredje elementet har lyfts upp ovanför de övriga. Det tredje, andra och första elementet har förflyttats åt höger.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra och tredje elementet är färgade blå. Det tredje elementet har lyfts upp ovanför de övriga. Det tredje, andra och första elementet har förflyttats åt höger. Elementet som lyftes upp befinner sig nu på första positionen.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra, tredje och fjärde elementet är färgade blå.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra, tredje och fjärde elementet är färgade blå. Det femte elementet har lyfts upp ovanför de övriga.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra, tredje och fjärde elementet är färgade blå. Det femte elementet har lyfts upp ovanför de övriga. Det fjärde elementet har förflyttats åt höger.

Datastrukturer och algoritmer i Python

Insertion sort

En schematisk representation av en lista med osorterade tal. Det första, andra, tredje och fjärde elementet är färgade blå. Det femte elementet har lyfts upp ovanför de övriga. Elementet som lyftes upp befinner sig nu på fjärde positionen.

Datastrukturer och algoritmer i 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
Datastrukturer och algoritmer i Python

Insertion sort – komplexitet

  • Värsta fall: $O(n^2)$
  • Genomsnittligt fall: $\Theta(n^2)$
  • Bästa fall: $\Omega(n)$
Datastrukturer och algoritmer i Python

Nu kör vi en övning!

Datastrukturer och algoritmer i Python

Preparing Video For Download...