Sortowanie przez wybieranie i wstawianie

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie

• Wyznacz najmniejszą wartość
• Zamień najmniejszą wartość z pierwszym nieuporządkowanym elementem

Sortowanie przez wybieranie – implementacja

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

Sortowanie przez wybieranie – złożoność

• Przypadek pesymistyczny: $O(n^2)$
• Przypadek średni: $\Theta(n^2)$
• Przypadek optymistyczny: $\Omega(n^2)$

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie – implementacja

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

Sortowanie przez wstawianie – złożoność

• Przypadek pesymistyczny: $O(n^2)$
• Przypadek średni: $\Theta(n^2)$
• Przypadek optymistyczny: $\Omega(n)$

Ćwiczenia!

Struktury danych i algorytmy w Pythonie