Sortare prin selecție și sortare prin inserție

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică primul element.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică primul element. Primul element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică al doilea element. Primul element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică al doilea element. Al doilea element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică al treilea element. Al doilea element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică al patrulea element. Al doilea element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică al patrulea element. Al patrulea element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Există un pointer care indică al cincilea element. Al patrulea element este colorat în portocaliu.

  • Determinați valoarea minimă
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Al patrulea element este colorat în portocaliu. Există două săgeți care indică faptul că primul și al patrulea element vor fi interschimbate.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în portocaliu. Primul și al patrulea element au fost interschimbate.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, iar al doilea în portocaliu. Există un pointer care indică al doilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, iar al doilea în portocaliu. Există un pointer care indică al treilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, iar al doilea în portocaliu. Există un pointer care indică al patrulea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, iar al doilea în portocaliu. Există un pointer care indică al cincilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru. Există un pointer care indică al treilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru, iar al treilea în portocaliu. Există un pointer care indică al treilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru, iar al treilea în portocaliu. Există un pointer care indică al patrulea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru, iar al patrulea în portocaliu. Există un pointer care indică al patrulea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru, iar al patrulea în portocaliu. Există un pointer care indică al cincilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru, iar al patrulea în portocaliu. Există două săgeți care indică faptul că al treilea și al patrulea element vor fi interschimbate.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru, iar al treilea în portocaliu. Al treilea și al patrulea element au fost interschimbate.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru. Există un pointer care indică al patrulea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru, iar al patrulea în portocaliu. Există un pointer care indică al patrulea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru, iar al patrulea în portocaliu. Există un pointer care indică al cincilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru, iar al cincilea în portocaliu. Există un pointer care indică al cincilea element.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru, iar al cincilea în portocaliu. Există două săgeți care indică faptul că al patrulea și al cincilea element vor fi interschimbate.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru, iar al patrulea în portocaliu. Al patrulea și al cincilea element au fost interschimbate.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în albastru.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție

O reprezentare schematică a unei liste cu numere neordonate. Toate elementele sunt colorate în albastru.

  • Determinați valoarea minimă
  • Interschimbați valoarea minimă cu primul element neordonat
Structuri de date și algoritmi în Python

Sortare prin selecție - implementare

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
Structuri de date și algoritmi în Python

Sortare prin selecție - complexitate

  • Cazul cel mai defavorabil: $O(n^2)$
  • Cazul mediu: $\Theta(n^2)$
  • Cazul cel mai favorabil: $\Omega(n^2)$
Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, iar al doilea a fost ridicat deasupra celorlalte.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul element este colorat în albastru, iar al doilea a fost ridicat deasupra celorlalte. Primul element a fost deplasat la dreapta.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Al doilea element este colorat în albastru. Elementul ridicat se află acum pe prima poziție.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul și al doilea element sunt colorate în albastru. Al treilea element a fost ridicat deasupra celorlalte.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru. Al treilea element a fost ridicat deasupra celorlalte.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru. Al treilea element a fost ridicat deasupra celorlalte. Al treilea element a fost deplasat la dreapta.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru. Al treilea element a fost ridicat deasupra celorlalte. Al treilea și al doilea element au fost deplasate la dreapta.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru. Al treilea element a fost ridicat deasupra celorlalte. Al treilea, al doilea și primul element au fost deplasate la dreapta.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea și al treilea element sunt colorate în albastru. Al treilea element a fost ridicat deasupra celorlalte. Al treilea, al doilea și primul element au fost deplasate la dreapta. Elementul ridicat se află acum pe prima poziție.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în albastru.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în albastru. Al cincilea element a fost ridicat deasupra celorlalte.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în albastru. Al cincilea element a fost ridicat deasupra celorlalte. Al patrulea element a fost deplasat la dreapta.

Structuri de date și algoritmi în Python

Sortare prin inserție

O reprezentare schematică a unei liste cu numere neordonate. Primul, al doilea, al treilea și al patrulea element sunt colorate în albastru. Al cincilea element a fost ridicat deasupra celorlalte. Elementul ridicat se află acum pe a patra poziție.

Structuri de date și algoritmi în Python

Sortare prin inserție - implementare

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
Structuri de date și algoritmi în Python

Sortare prin inserție - complexitate

  • Cazul cel mai defavorabil: $O(n^2)$
  • Cazul mediu: $\Theta(n^2)$
  • Cazul cel mai favorabil: $\Omega(n)$
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...