Řazení výběrem a vkládáním

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na první prvek.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na první prvek. První prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na druhý prvek. První prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na druhý prvek. Druhý prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na třetí prvek. Druhý prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na čtvrtý prvek. Druhý prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na čtvrtý prvek. Čtvrtý prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Ukazatel míří na pátý prvek. Čtvrtý prvek je oranžový.

  • Nalezení nejmenší hodnoty
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Čtvrtý prvek je oranžový. Dvě šipky znázorňují prohození prvního a čtvrtého prvku.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První prvek je oranžový. První a čtvrtý prvek byly prohozeny.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První prvek je modrý a druhý prvek je oranžový. Ukazatel míří na druhý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První prvek je modrý a druhý prvek je oranžový. Ukazatel míří na třetí prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První prvek je modrý a druhý prvek je oranžový. Ukazatel míří na čtvrtý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První prvek je modrý a druhý prvek je oranžový. Ukazatel míří na pátý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré. Ukazatel míří na třetí prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré a třetí prvek je oranžový. Ukazatel míří na třetí prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré a třetí prvek je oranžový. Ukazatel míří na čtvrtý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré a čtvrtý prvek je oranžový. Ukazatel míří na čtvrtý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré a čtvrtý prvek je oranžový. Ukazatel míří na pátý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré a čtvrtý prvek je oranžový. Dvě šipky znázorňují prohození třetího a čtvrtého prvku.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré a třetí prvek je oranžový. Třetí a čtvrtý prvek byly prohozeny.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré. Ukazatel míří na čtvrtý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré a čtvrtý prvek je oranžový. Ukazatel míří na čtvrtý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré a čtvrtý prvek je oranžový. Ukazatel míří na pátý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré a pátý prvek je oranžový. Ukazatel míří na pátý prvek.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré a pátý prvek je oranžový. Dvě šipky znázorňují prohození čtvrtého a pátého prvku.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré a čtvrtý prvek je oranžový. Čtvrtý a pátý prvek byly prohozeny.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. První, druhý, třetí a čtvrtý prvek jsou modré.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem

Schématické znázornění seznamu s neseřazenými čísly. Všechny prvky jsou modré.

  • Nalezení nejmenší hodnoty
  • Prohození nejmenší hodnoty s prvním neseřazeným prvkem
Datové struktury a algoritmy v Pythonu

Řazení výběrem – implementace

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

Řazení výběrem – složitost

  • Nejhorší případ: $O(n^2)$
  • Průměrný případ: $\Theta(n^2)$
  • Nejlepší případ: $\Omega(n^2)$
Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První prvek je modrý a druhý prvek byl vyzdvižen nad ostatní.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První prvek je modrý a druhý prvek byl vyzdvižen nad ostatní. První prvek byl posunut doprava.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. Druhý prvek je modrý. Vyzdvižený prvek je nyní na první pozici.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První a druhý prvek jsou modré. Třetí prvek byl vyzdvižen nad ostatní.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré. Třetí prvek byl vyzdvižen nad ostatní.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré. Třetí prvek byl vyzdvižen nad ostatní. Třetí prvek byl posunut doprava.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré. Třetí prvek byl vyzdvižen nad ostatní. Třetí a druhý prvek byly posunuty doprava.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré. Třetí prvek byl vyzdvižen nad ostatní. Třetí, druhý a první prvek byly posunuty doprava.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý a třetí prvek jsou modré. Třetí prvek byl vyzdvižen nad ostatní. Třetí, druhý a první prvek byly posunuty doprava. Vyzdvižený prvek je nyní na první pozici.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý, třetí a čtvrtý prvek jsou modré.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý, třetí a čtvrtý prvek jsou modré. Pátý prvek byl vyzdvižen nad ostatní.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý, třetí a čtvrtý prvek jsou modré. Pátý prvek byl vyzdvižen nad ostatní. Čtvrtý prvek byl posunut doprava.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním

Schématické znázornění seznamu s neseřazenými čísly. První, druhý, třetí a čtvrtý prvek jsou modré. Pátý prvek byl vyzdvižen nad ostatní. Vyzdvižený prvek je nyní na čtvrté pozici.

Datové struktury a algoritmy v Pythonu

Řazení vkládáním – implementace

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

Řazení vkládáním – složitost

  • Nejhorší případ: $O(n^2)$
  • Průměrný případ: $\Theta(n^2)$
  • Nejlepší případ: $\Omega(n)$
Datové struktury a algoritmy v Pythonu

Lass uns üben!

Datové struktury a algoritmy v Pythonu

Preparing Video For Download...