Алгоритмы сортировки

Контакты в телефоне стоят по алфавиту, таблица рекордов в игре — по очкам, товары в интернет-магазине можно выстроить по цене. Во всех этих случаях компьютер выполняет сортировку — расставляет элементы по порядку согласно какому-то правилу. К тому же, как мы видели на прошлом уроке, быстрый двоичный поиск работает только с упорядоченным списком. Так как же компьютер сортирует список?

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

При сортировке пузырьком соседние элементы сравниваются попарно: если левый больше правого, они меняются местами. Просмотр списка от начала до конца называется проходом. После каждого прохода самый большой из оставшихся элементов, как пузырёк в воде, «всплывает» в конец списка. Если за проход не было ни одной перестановки, список уже отсортирован.

def bubble_sort(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

print(bubble_sort([5, 1, 4, 2]))
print(sorted(['Murad', 'Aysel', 'Leyla', 'Elvin']))

[1, 2, 4, 5]
['Aysel', 'Elvin', 'Leyla', 'Murad']

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

При сортировке выбором в неотсортированной части списка находят наименьший элемент и меняют его местами с первым элементом этой части. Так отсортированная часть слева на каждом шаге растёт на один элемент.

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

Сортировка вставками похожа на то, как игрок раскладывает карты в руке: берёт следующую карту и вставляет её на нужное место среди уже упорядоченных. Этот способ работает очень быстро, если список почти отсортирован.

Какой алгоритм быстрее?

Скорость сортировки обычно измеряют числом сравнений. Каждый из трёх простых способов в худшем случае выполняет около n(n − 1) / 2 сравнений: 45 при n = 10 и уже 499 500 при n = 1000. Если список станет в 10 раз длиннее, работа вырастет примерно в 100 раз!