Bubble sort

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Řadicí algoritmy

  • Hojně studované
  • Řeší řazení neseřazené kolekce ve vzestupném/sestupném pořadí
  • Mohou snížit složitost problémů
  • Příklady řadicích algoritmů:
    • bubble sort
    • selection sort
    • insertion sort
    • merge sort
    • quicksort
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek.

  • První hodnota větší než druhá
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. První a druhý prvek byly prohozeny.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na druhý prvek, druhý na třetí prvek.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na třetí prvek, druhý na čtvrtý prvek.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na třetí prvek, druhý na čtvrtý prvek. Třetí a čtvrtý prvek byly prohozeny.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na čtvrtý prvek, druhý na pátý prvek.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na čtvrtý prvek, druhý na pátý prvek. Čtvrtý a pátý prvek byly prohozeny.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na čtvrtý prvek, druhý na pátý prvek. Pátý prvek je modrý, protože je seřazen.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. Poslední prvek je modrý.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na druhý prvek, druhý na třetí prvek. Poslední prvek je modrý.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na druhý prvek, druhý na třetí prvek. Druhý a třetí prvek byly prohozeny. Poslední prvek je modrý.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na třetí prvek, druhý na čtvrtý prvek. Poslední prvek je modrý.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na třetí prvek, druhý na čtvrtý prvek. Poslední dva prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. Poslední dva prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. První a druhý prvek byly prohozeny. Poslední dva prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na druhý prvek, druhý na třetí prvek. Poslední dva prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na druhý prvek, druhý na třetí prvek. Poslední tři prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. Poslední tři prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. Poslední čtyři prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort

Schematické znázornění seznamu s neseřazenými čísly. Jeden ukazatel míří na první prvek, druhý na druhý prvek. Všechny prvky jsou modré.

  • První hodnota větší než druhá
    • Prohodit je
  • Druhá hodnota větší než první
    • Nic
Datové struktury a algoritmy v Pythonu

Bubble sort – implementace

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]
Datové struktury a algoritmy v Pythonu

Bubble sort – implementace

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
Datové struktury a algoritmy v Pythonu

Bubble sort – složitost

  • Nejhorší případ: $O(n^2)$
  • Nejlepší případ – základní verze: $\Omega(n^2)$
  • Nejlepší případ – vylepšená verze: $\Omega(n)$
  • Průměrný případ: $\Theta(n^2)$
  • Nevhodný pro velké silně neseřazené seznamy
  • Vhodný pro:
    • velké seřazené/téměř seřazené seznamy
    • malé seznamy
Datové struktury a algoritmy v Pythonu

Pojďme si procvičit!

Datové struktury a algoritmy v Pythonu

Preparing Video For Download...