Сортування бульбашкою

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

Miriam Antona

Software engineer

Алгоритми сортування

  • Глибоко вивчили
  • Розв'язує, як відсортувати невпорядковану колекцію за зростанням/спаданням
  • Може зменшити складність задач
  • Деякі алгоритми сортування:
    • bubble sort
    • selection sort
    • insertion sort
    • merge sort
    • quicksort
Структури даних і алгоритми в 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...