Сортировка пузырьком, выбором и вставками; сравнение сложности алгоритмов
Задача сортировки
Сортировкой называют задачу перестановки элементов массива в определённом порядке — как правило, по неубыванию (от меньшего к большему) или по невозрастанию. Сортировка — одна из самых востребованных операций при обработке данных: многие алгоритмы (например, бинарный поиск) требуют предварительно отсортированного массива, а отсортированные данные проще анализировать и представлять. Существует множество алгоритмов сортировки, различающихся по скорости работы, требуемой дополнительной памяти и простоте реализации; в этом разделе рассмотрены три классических «простых» алгоритма: сортировка пузырьком, выбором и вставками.
Сортировка пузырьком (bubble sort)
Сортировка пузырьком — самый наглядный (хотя и не самый эффективный) алгоритм: он многократно проходит по массиву, сравнивая каждую пару соседних элементов, и меняет их местами, если они стоят в неправильном порядке. За каждый полный проход самый большой из ещё не отсортированных элементов «всплывает», подобно пузырьку, в свою окончательную позицию в конце массива — отсюда и название алгоритма.
def bubble_sort(a):
n = len(a)
for i in range(n — 1):
for j in range(n — 1 — i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j] # обмен местами
return a
data = [8, 3, 15, 6, 42, 9, 21]
print(bubble_sort(data)) # [3, 6, 8, 9, 15, 21, 42]
Внешний цикл выполняется n−1 раз (число полных проходов), а внутренний цикл на каждом проходе сравнивает пары соседних элементов — суммарно выполняется порядка n²/2 сравнений, поэтому временная сложность сортировки пузырьком квадратична.
Сортировка выбором (selection sort)
Сортировка выбором на каждом шаге находит минимальный элемент среди ещё не отсортированной части массива и меняет его местами с первым элементом этой части. Таким образом, после i-го шага первые i элементов массива гарантированно стоят на своих окончательных местах в отсортированном порядке.
def selection_sort(a):
n = len(a)
for i in range(n — 1):
min_index = i
for j in range(i + 1, n):
if a[j] < a[min_index]:
min_index = j
a[i], a[min_index] = a[min_index], a[i] # обмен местами
return a
data = [8, 3, 15, 6, 42, 9, 21]
print(selection_sort(data)) # [3, 6, 8, 9, 15, 21, 42]
В отличие от сортировки пузырьком, при сортировке выбором обмен элементов местами происходит не более n−1 раз (один раз на каждый шаг внешнего цикла), что может быть выгодно, если сама операция обмена «дорогая». Однако число сравнений при поиске минимума остаётся того же порядка, и общая сложность алгоритма также квадратична.
Сортировка вставками (insertion sort)
Сортировка вставками строит отсортированную часть массива постепенно, слева направо: на каждом шаге очередной элемент «вынимается» из неотсортированной части и вставляется на нужное место среди уже отсортированных элементов слева от него, сдвигая при необходимости более крупные элементы на одну позицию вправо. Этот способ похож на то, как человек сортирует карты в руке.
def insertion_sort(a):
n = len(a)
for i in range(1, n):
key = a[i] # элемент, который нужно вставить
j = i — 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j] # сдвигаем больший элемент вправо
j -= 1
a[j + 1] = key # вставляем элемент на освободившееся место
return a
data = [8, 3, 15, 6, 42, 9, 21]
print(insertion_sort(data)) # [3, 6, 8, 9, 15, 21, 42]
Сортировка вставками в худшем случае (массив отсортирован в обратном порядке) также требует порядка n²/2 сравнений и сдвигов, поэтому имеет квадратичную сложность, однако на почти отсортированных массивах она работает значительно быстрее, чем сортировка пузырьком или выбором, что делает её практически полезной для небольших или частично упорядоченных наборов данных.
Улучшение сортировки пузырьком: ранний выход из цикла
Базовую сортировку пузырьком можно немного улучшить: если за очередной полный проход по массиву не произошло ни одного обмена элементов местами, это означает, что массив уже отсортирован и дальнейшие проходы бессмысленны — цикл можно прервать досрочно оператором break. Такая модификация не меняет сложность алгоритма в худшем случае, но заметно ускоряет его работу на уже отсортированных или почти отсортированных массивах.
def bubble_sort_optimized(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_optimized([1, 2, 3, 4, 5])) # уже отсортирован, 1 проход
print(bubble_sort_optimized([5, 4, 3, 2, 1])) # требуется полная сортировка
Оценка сложности алгоритмов: O-нотация
Чтобы сравнивать эффективность разных алгоритмов независимо от конкретного компьютера, на котором они выполняются, используют асимптотическую (O-) нотацию: она показывает, как растёт время работы алгоритма (число элементарных операций) при увеличении размера входных данных n, отбрасывая постоянные множители и менее значимые слагаемые. Ниже перечислены основные классы сложности от самых быстрых к самым медленным.
| Обозначение | Название | Пример алгоритма |
|---|---|---|
O(1) | постоянная сложность | обращение к элементу массива по индексу |
O(log₂n) | логарифмическая сложность | бинарный поиск в отсортированном массиве |
O(n) | линейная сложность | линейный поиск, суммирование элементов массива |
O(n·log₂n) | линейно-логарифмическая сложность | быстрая сортировка, сортировка слиянием |
O(n²) | квадратичная сложность | сортировка пузырьком, выбором, вставками |
Чем медленнее растёт функция сложности, тем лучше алгоритм масштабируется на большие объёмы данных: разница между O(n) и O(n²) для массива из 10000 элементов — это разница между примерно 10000 и 100 000 000 операциями, то есть в 10000 раз.
Сравнение изученных алгоритмов сортировки
| Алгоритм | Сложность (худший случай) | Особенность |
|---|---|---|
Сортировка пузырьком | O(n²) | самый простой для понимания, но обычно самый медленный на практике |
Сортировка выбором | O(n²) | минимальное число обменов элементов местами |
Сортировка вставками | O(n²) | эффективна на почти отсортированных массивах |
Быстрая сортировка (для сравнения) | в среднем O(n·log₂n) | один из самых быстрых универсальных алгоритмов на практике |
Встроенная сортировка в Python
В реальных программах вручную реализованные алгоритмы сортировки почти не используются — вместо них применяют встроенные, уже оптимизированные средства языка: метод списка a.sort() сортирует список «на месте» (изменяя исходный список), а функция sorted(a) возвращает новый отсортированный список, не изменяя исходный. Оба средства принимают необязательный параметр reverse=True для сортировки по убыванию и параметр key для сортировки по вычисляемому признаку.
data = [8, 3, 15, 6, 42, 9, 21]
data.sort()
print(data) # [3, 6, 8, 9, 15, 21, 42]
words = ['банан', 'яблоко', 'груша', 'арбуз']
print(sorted(words)) # по алфавиту
print(sorted(words, key=len)) # по длине слова
print(sorted(words, reverse=True)) # по убыванию
Типичные ошибки
Частая ошибка в сортировке пузырьком и выбором — неверные границы внутреннего цикла, приводящие либо к выходу за пределы массива (IndexError при сравнении a[j] и a[j+1], если j доходит до len(a)-1), либо к неполной сортировке. Вторая ошибка — забыть, что обмен местами в Python выполняется одной строкой a[i], a[j] = a[j], a[i], и пытаться сделать это через одну промежуточную переменную неправильно (перезаписав значение до его сохранения). Третья ошибка — путать метод sort() (сортирует список на месте и возвращает None) с функцией sorted() (возвращает новый список): запись data = data.sort() приведёт к тому, что переменная data станет равна None. Наконец, при сравнении алгоритмов часто ошибочно считают, что все алгоритмы сортировки имеют одинаковую сложность — на самом деле выбор алгоритма существенно влияет на быстродействие программы при больших объёмах данных.
Краткий словарь терминов
Сортировка — упорядочивание элементов массива по возрастанию или убыванию.
Сортировка пузырьком — алгоритм сортировки, многократно сравнивающий и меняющий местами соседние элементы.
Сортировка выбором — алгоритм, на каждом шаге выбирающий минимальный элемент неотсортированной части и ставящий его на своё место.
Сортировка вставками — алгоритм, вставляющий очередной элемент на нужное место среди уже отсортированных.
O-нотация — способ оценки роста времени работы алгоритма в зависимости от размера входных данных.
Квадратичная сложность O(n²) — класс сложности, при котором время работы алгоритма растёт пропорционально квадрату числа элементов.
Заключение
Сортировка пузырьком, выбором и вставками — простые для понимания, но неэффективные на больших массивах алгоритмы с квадратичной сложностью O(n²); понимание того, как считать и сравнивать сложность алгоритмов, — важный навык для анализа и выбора подходящего инструмента решения задачи. Полученные представления о структурах данных и алгоритмах естественно подводят к следующему шагу — объектно-ориентированному программированию, которое позволяет объединять данные и обрабатывающие их алгоритмы в единые сущности — объекты.
