Сортировка выбором и сортировка вставками

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

Miriam Antona

Software engineer

Сортировка выбором

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

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

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

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

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

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Один указатель указывает на второй элемент. Второй элемент выделен оранжевым цветом.

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Один указатель указывает на третий элемент. Второй элемент выделен оранжевым цветом.

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Один указатель указывает на четвёртый элемент. Второй элемент выделен оранжевым цветом.

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Один указатель указывает на четвёртый элемент. Четвёртый элемент выделен оранжевым цветом.

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Один указатель указывает на пятый элемент. Четвёртый элемент выделен оранжевым цветом.

  • Определить наименьшее значение
Структуры данных и алгоритмы на Python

Сортировка выбором

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

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

Сортировка выбором

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

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым цветом. Один указатель указывает на второй элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым цветом. Один указатель указывает на третий элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым цветом. Один указатель указывает на четвёртый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый элемент выделен синим, второй — оранжевым цветом. Один указатель указывает на пятый элемент.

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

Сортировка выбором

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

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый и второй элементы выделены синим, третий — оранжевым цветом. Один указатель указывает на третий элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый и второй элементы выделены синим, третий — оранжевым цветом. Один указатель указывает на четвёртый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый и второй элементы выделены синим, четвёртый — оранжевым цветом. Один указатель указывает на четвёртый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый и второй элементы выделены синим, четвёртый — оранжевым цветом. Один указатель указывает на пятый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый и второй элементы выделены синим, четвёртый — оранжевым цветом. Две стрелки показывают, что третий и четвёртый элементы будут поменяны местами.

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

Сортировка выбором

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

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены синим цветом. Один указатель указывает на четвёртый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены синим, четвёртый — оранжевым цветом. Один указатель указывает на четвёртый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены синим, четвёртый — оранжевым цветом. Один указатель указывает на пятый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены синим, пятый — оранжевым цветом. Один указатель указывает на пятый элемент.

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

Сортировка выбором

Схематическое изображение списка с неупорядоченными числами. Первый, второй и третий элементы выделены синим, пятый — оранжевым цветом. Две стрелки показывают, что четвёртый и пятый элементы будут поменяны местами.

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

Сортировка выбором

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

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

Сортировка выбором

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

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

Сортировка выбором

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

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

Сортировка выбором — реализация

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

Сортировка выбором — сложность

  • Худший случай: $O(n^2)$
  • Средний случай: $\Theta(n^2)$
  • Лучший случай: $\Omega(n^2)$
Структуры данных и алгоритмы на Python

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

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

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

Сортировка вставками

Схематическое изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены синим цветом. Пятый элемент поднят над остальными.

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

Сортировка вставками

Схематическое изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены синим цветом. Пятый элемент поднят над остальными. Четвёртый элемент сдвинут вправо.

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

Сортировка вставками

Схематическое изображение списка с неупорядоченными числами. Первый, второй, третий и четвёртый элементы выделены синим цветом. Пятый элемент поднят над остальными. Поднятый элемент теперь стоит на четвёртой позиции.

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

Сортировка вставками — реализация

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

Сортировка вставками — сложность

  • Худший случай: $O(n^2)$
  • Средний случай: $\Theta(n^2)$
  • Лучший случай: $\Omega(n)$
Структуры данных и алгоритмы на Python

Давайте потренируемся!

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

Preparing Video For Download...