​​Сортировка пузырьком

Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [3, 1, 4, 2] → [1, 2, 3, 4].

Смысл пузырьковой сортировки заключается в следующем: мы начинаем с начала списка и сравниваем элементы попарно (нулевой и первый), если нулевой больше первого, то меняем их местами. Независимо от того, была ли замена или нет, мы шагаем вправо и сравниваем элементы вновь. Если на прошлом шаге была замена, то на этом шаге у нас окажется тот же элемент, и если он опять оказался больше, то «всплывет» снова вправо. Так за один проход наибольший элемент всплывет в самый-самый конец списка, подобно тому, как пузырек воздуха всплывает в бутылке воды. Когда все пузырьки всплывут – список будет отсортирован.

📎 Пример: a = [3, 1, 4, 2] – 4 элемента:

Первый проход:
  1. Сравним a[0] = 3 и a[1] = 1, 3 > 1. Меняем их местами. Теперь a = [1, 3, 4, 2].
  2. Сравним a[1] = 3 и a[2] = 4, 3 < 4. Менять не надо.
  3. Сравним a[2] = 4 и a[3] = 2, 4 > 2. Меняем. a = [1, 3, 2, 4].

Проход окончен. 4 «всплыла» в самый конец списка на свое место a[3]. Поэтому мы не трогаем больше конец списка, но список еще не отсортирован до конца, и следующий проход будет рассматривать только первые 3 элемента списка.

Второй проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо.
  2. Сравним a[1] = 3 и a[2] = 2, 3 > 2. Меняем их. a = [1, 2, 3, 4]. Проход окончен.
Третий проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо. Список отсортирован. Можно выходить.

👨‍💻 Переходим к реализации на Python:

def bubble_sort(a):
    n = len(a)
    
    # номер прохода i = 0..(n-2), т.е. (n-1 раз):
    for i in range(n - 1):
        # номер сравнения j = 0..(n - i - 2)
        for j in range(n - i - 1):
            # сравниваем только соседние элементы
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

Алгоритм прост, но можно запутаться в индексах: с какого элемента и куда бежать, что с чем сравнивать. Как лучше запомнить:

  • Начинаем всегда с начала (0-го элемента).
  • Число проходов меньше на 1, чем число элементов
  • С каждым проходом мы делаем все меньше и меньше сравнений, так как сортированный хвост списка растет на 1 после каждого прохода
  • Сравниваем только соседние элементы a[j] > a[j + 1], (а не i и j).
  • Если знак сравнения перевернуть, то сортировка будет по убыванию.

Временная сложность алгоритма квадратичная O(n^2) – имеются два вложенных цикла по элементам. Поэтому алгоритм медлителен для больших списков.  В реальной жизни чаще применяются другие алгоритмы сортировки, но пузырек до сих пор не забывают преподавать и спрашивать.

🐉 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Куча и очередь с приоритетом

Порядок обхода кучи

Очередь с приоритетом – это такая коллекция, которая поддерживает обязательно две следующие операции: вставка элемента с некоторым приоритетом (это может быть число или другой сравнимый объект) и извлечение элемента с наибольшим (или наименьшим приоритетом).

ЧИТАТЬ ПОДРОБНЕЕ

🔀 Встроенная сортировка Python

В Python сортировка производится встроенной функцией sorted. Первым аргументом она принимает итерируемый объект. Это может быть список, кортеж, генератор, итератор и т.п. Возвращает отсортированный список.

>>> sorted([4, 2, 3, 1, 0])
[0, 1, 2, 3, 4]

>>> sorted((3, 1, 2))
[1, 2, 3]

>>> sorted(x * x for x in range(-5, 6))
[0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25]

Для словаря вернет сортированный список ключей:

>>> sorted({1: "abc", 3: "foo", -1: "baz"}) 
[-1, 1, 3] 

Если хотим значение, надо прямо это указать:

>>> sorted({1: "abc", 3: "foo", -1: "baz"}.values())
['abc', 'baz', 'foo']

Можно сортировать в обратном порядке:

>>> sorted([4, 2, 3, 1, 0], reverse=True)
[4, 3, 2, 1, 0]

Если сортируемые элементы – списки, словари или объекты, то воспользуемся параметром key. Мы передаем в key нечто вызываемое (имя функции, lambda и т.п), и при сортировки элементы сравниваются по результату вызова key на элементе. Результатом key должно быть число, строка или что-то другое сравнимое между собой.

📎 Пример. Сортировка списка строк по длине строки:

>>> sorted(["foo", "bazooka", "", "game"], key=len)
['', 'foo', 'game', 'bazooka']

📎 Пример. Сортировка списка кортежей по 0 или 1 элементу каждого.

>>> people = [("Bill", "Gates"), ("Tim", "Cook"), ("Donald", "Trump")]

>>> sorted(people, key=lambda t: t[0])
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]

>>> sorted(people, key=lambda t: t[1])
[('Tim', 'Cook'), ('Bill', 'Gates'), ('Donald', 'Trump')]

Для этой же цели удобно использовать функцию operator.itemgetter:

>>> import operator
>>> sorted(people, key=operator.itemgetter(0))
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]

Еще полезные функции из operator:
attrgetter(name) – для получение значения атрибута объекта с именем name
methodcaller(name[, args…]) – для получения результата вызова метода name у объекта. Опционально с аргументами args.

Вот пример использования этих функций:

import operator

class Item:
    def __init__(self, name, price, qty):
        self.name = name
        self.price = price
        self.qty = qty

    def total_cost(self):
        return self.price * self.qty

    def __repr__(self):
        return f'({self.name} ${self.price} x {self.qty} = ${self.total_cost()})'


items = [
    Item("iPhone", 999, 5),
    Item("iMac", 2999, 2),
    Item("iPad", 599, 11)
]

def print_items(title, item_list):
    print(title)
    print(*item_list, sep=', ', end='\n\n')


print_items('Original:', items)

items_by_price = sorted(items, key=operator.attrgetter('price'))
print_items('Sorted by price:', items_by_price)

items_by_total_cost = sorted(items, key=operator.methodcaller('total_cost'))
print_items('Sorted by total cost:', items_by_total_cost)

"""
Original:
(iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589)
Sorted by price:
(iPad $599 x 11 = $6589), (iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998)
Sorted by total cost:
(iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589)
"""

Для списков (list) определен метод sort(), который модифицирует исходный список, выстраивая элемента по порядку.

>>> arr = [3, 4, 1, 2, 5, 6, 0]
>>> arr.sort()
>>> arr
[0, 1, 2, 3, 4, 5, 6]

Сортировка в Python – устойчива. Это значит, что порядок элементов с одинаковыми ключами будет сохранен в сортированной последовательности:

>>> names = ["John", "Tim", "Bill", "Max"]
>>> sorted(names, key=len)
['Tim', 'Max', 'John', 'Bill']

Tim и Max — оба длины 3, Tim был перед Max, так и осталось. John остался перед Bill. Зачем это нужно? Чтобы можно было сортировать сначала по одному признаку, потому по другому (если первый совпадает).

📎 Пример. Первичный признак – оценка ученика. Вторичный – имя. Внимание: сначала сортируем по вторичному, потому по первичному:

>>> students = [(3, "Xi"), (5, "Kate"), (5, "Max"), (3, "Fil"), (5, "Abby")]
>>> students_by_name = sorted(students, key=operator.itemgetter(1))
>>> sorted(students_by_name, key=operator.itemgetter(0))
[(3, 'Fil'), (3, 'Xi'), (5, 'Abby'), (5, 'Kate'), (5, 'Max')]

Внутри Python использует Timsort – гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Смысл в том, что в реальном мире часто встречаются частично отсортированные данные, на которых Timsort работает ощутимо быстрее прочих алгоритмов сортировки. Сложность по времени: O(n log n) в худшем случае и O(n) – в лучшем.

⚠️ CPython: не пытайтесь модифицировать сортируемый список во время сортировки. Эффект непредсказуем.

Специально для канала @pyway.