Sortarea prin bule

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Algoritmi de sortare

  • Studiate aprofundat
  • Rezolvă cum să sortați o colecție neordonată în ordine crescătoare/descrescătoare
  • Pot reduce complexitatea problemelor
  • Câțiva algoritmi de sortare:
    • sortare prin bule
    • sortare prin selecție
    • sortare prin inserție
    • sortare prin interclasare
    • quicksort
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element.

  • Prima valoare mai mare decât a doua
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Primul și al doilea element au fost interschimbate.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al doilea element, iar altul indică al treilea element.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al treilea element, iar altul indică al patrulea element.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al treilea element, iar altul indică al patrulea element. Al treilea și al patrulea element au fost interschimbate.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al patrulea element, iar altul indică al cincilea element.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al patrulea element, iar altul indică al cincilea element. Al patrulea și al cincilea element au fost interschimbate.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al patrulea element, iar altul indică al cincilea element. Al cincilea element este colorat în albastru, deoarece este ordonat.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Ultimul element este colorat în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al doilea element, iar altul indică al treilea element. Ultimul element este colorat în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al doilea element, iar altul indică al treilea element. Al doilea și al treilea element au fost interschimbate. Ultimul element este colorat în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al treilea element, iar altul indică al patrulea element. Ultimul element este colorat în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al treilea element, iar altul indică al patrulea element. Ultimele două elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Ultimele două elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Primul și al doilea element au fost interschimbate. Ultimele două elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al doilea element, iar altul indică al treilea element. Ultimele două elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică al doilea element, iar altul indică al treilea element. Ultimele trei elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Ultimele trei elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Ultimele patru elemente sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortarea prin bule

O reprezentare schematică a unei liste cu numere neordonate. Un pointer indică primul element, iar altul indică al doilea element. Toate elementele sunt colorate în albastru.

  • Prima valoare mai mare decât a doua
    • Interschimbați-le
  • A doua valoare mai mare decât prima
    • Nimic
Structuri de date și algoritmi în Python

Sortare prin bule - implementare

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

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Structuri de date și algoritmi în Python

Sortare prin bule - implementare

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Structuri de date și algoritmi în Python

Sortare prin bule - complexitate

  • Cazul cel mai defavorabil: $O(n^2)$
  • Cazul cel mai favorabil - versiune neîmbunătățită: $\Omega(n^2)$
  • Cazul cel mai favorabil - versiune îmbunătățită: $\Omega(n)$
  • Cazul mediu: $\Theta(n^2)$
  • Performanță slabă pe liste mari, foarte neordonate
  • Performanță bună pentru:
    • liste mari sortate/aproape sortate
    • liste mici
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...