Пузырьковая сортировка

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

Пузырьковая сортировка – реализация

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

Пузырьковая сортировка – реализация

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

Пузырьковая сортировка – сложность

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

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

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

Preparing Video For Download...