Сортування вибором і вставкою

Структури даних і алгоритми в Python

Miriam Antona

Software engineer

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на перший елемент.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на перший елемент. Перший елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на другий елемент. Перший елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на другий елемент. Другий елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на третій елемент. Другий елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на четвертий елемент. Другий елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на четвертий елемент. Четвертий елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Є вказівник на п'ятий елемент. Четвертий елемент виділено помаранчевим.

  • Знайдіть найменше значення
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Четвертий елемент виділено помаранчевим. Дві стрілки показують, що перший і четвертий елементи буде поміняно місцями.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено помаранчевим. Перший і четвертий елементи вже поміняно місцями.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено синім, другий — помаранчевим. Є вказівник на другий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено синім, другий — помаранчевим. Є вказівник на третій елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено синім, другий — помаранчевим. Є вказівник на четвертий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено синім, другий — помаранчевим. Є вказівник на п'ятий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім. Є вказівник на третій елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім, третій — помаранчевим. Є вказівник на третій елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім, третій — помаранчевим. Є вказівник на четвертий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім, четвертий — помаранчевим. Є вказівник на четвертий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім, четвертий — помаранчевим. Є вказівник на п'ятий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім, четвертий — помаранчевим. Дві стрілки показують, що третій і четвертий елементи буде поміняно місцями.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім, третій — помаранчевим. Третій і четвертий елементи вже поміняно місцями.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім. Є вказівник на четвертий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім, четвертий — помаранчевим. Є вказівник на четвертий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім, четвертий — помаранчевим. Є вказівник на п'ятий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім, п'ятий — помаранчевим. Є вказівник на п'ятий елемент.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім, п'ятий — помаранчевим. Дві стрілки показують, що четвертий і п'ятий елементи буде поміняно місцями.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім, четвертий — помаранчевим. Четвертий і п'ятий елементи вже поміняно місцями.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий, третій і четвертий елементи виділено синім.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort

Схематичне зображення списку з неупорядкованими числами. Усі елементи виділено синім.

  • Знайдіть найменше значення
  • Поміняйте його з першим не відсортованим елементом
Структури даних і алгоритми в Python

Selection sort — реалізація

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
Структури даних і алгоритми в Python

Selection sort — складність

  • Найгірший випадок: $O(n^2)$
  • Середній випадок: $\Theta(n^2)$
  • Найкращий випадок: $\Omega(n^2)$
Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено синім, другий піднято над іншими.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший елемент виділено синім, другий піднято над іншими. Перший елемент зсунено праворуч.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Другий елемент виділено синім. Піднятий елемент тепер на першій позиції.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший і другий елементи виділено синім. Третій елемент піднято над іншими.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім. Третій елемент піднято над іншими.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім. Третій елемент піднято над іншими. Третій елемент зсунено праворуч.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім. Третій елемент піднято над іншими. Третій і другий елементи зсунено праворуч.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім. Третій елемент піднято над іншими. Третій, другий і третій елементи зсунено праворуч.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий і третій елементи виділено синім. Третій елемент піднято над іншими. Третій, другий і третій елементи зсунено праворуч. Піднятий елемент тепер на першій позиції.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий, третій і четвертий елементи виділено синім.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий, третій і четвертий елементи виділено синім. П'ятий елемент піднято над іншими.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий, третій і четвертий елементи виділено синім. П'ятий елемент піднято над іншими. Четвертий елемент зсунено праворуч.

Структури даних і алгоритми в Python

Insertion sort

Схематичне зображення списку з неупорядкованими числами. Перший, другий, третій і четвертий елементи виділено синім. П'ятий елемент піднято над іншими. Піднятий елемент тепер на четвертій позиції.

Структури даних і алгоритми в Python

Insertion sort — реалізація

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
Структури даних і алгоритми в Python

Insertion sort — складність

  • Найгірший випадок: $O(n^2)$
  • Середній випадок: $\Theta(n^2)$
  • Найкращий випадок: $\Omega(n)$
Структури даних і алгоритми в Python

Давайте потренуємось!

Структури даних і алгоритми в Python

Preparing Video For Download...