Сортировка пузырьком и сортировка вставками
Напишите оба алгоритма квадратичной сортировки, поймите, почему они имеют сложность O(n²), и узнайте об единственном случае, когда сортировка вставками превосходит сортировку слиянием
«Сортировка пузырьком и сортировка вставками» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Зачем изучать сортировки O(n²)
Сортировка пузырьком и сортировка вставками имеют сложность O(n²) в худшем случае, поэтому непрактичны для больших входных данных. И всё же на каждом серьёзном собеседовании по алгоритмам ожидается, что вы сможете реализовать и проанализировать их. Эти алгоритмы обучают фундаментальным понятиям — сравнению, обмену, устойчивой сортировке и поведению в лучшем случае, — которые применимы и к более сложным алгоритмам. Интервьюеры используют их, чтобы проверить, умеете ли вы рассуждать об инвариантах циклов и асимптотических обозначениях с самых основ.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Сортировка пузырьком: всплытие максимума
Сортировка пузырьком многократно просматривает массив и меняет местами соседние элементы, расположенные не по порядку. После каждого полного прохода самый большой неотсортированный элемент «всплывает» на своё окончательное место в конце массива. После n-1 проходов весь массив отсортирован. Название связано с тем, как большие элементы поднимаются вверх подобно пузырькам. Это самый простой для объяснения алгоритм сортировки, но на практике его используют редко.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Сортировка пузырьком с досрочным завершением
Оптимизированная сортировка пузырьком использует флаг swapped: если полный проход внутреннего цикла не приводит ни к одному обмену, массив уже отсортирован, и мы досрочно завершаем работу. Это даёт O(n) в лучшем случае для уже отсортированных входных данных — единственное настоящее преимущество сортировки пузырьком. Без этого флага алгоритм всегда выполняет O(n²) сравнений. Именно оптимизацию с досрочным завершением проверяют интервьюеры, когда спрашивают об улучшении сортировки пузырьком.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passАнализ сложности сортировки пузырьком
Внешний цикл сортировки пузырьком выполняется n-1 раз. Внутренний цикл выполняется n-1-i раз за проход: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 сравнений. Это даёт O(n²) в среднем и в худшем случае. С флагом досрочного завершения сложность в лучшем случае снижается до O(n) для отсортированных входных данных. Пространственная сложность равна O(1) — только для обмена нужна временная переменная. Сортировка пузырьком является устойчивой: равные элементы сохраняют взаимный порядок, поскольку мы меняем местами только элементы, которые строго больше соседних.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Сортировка вставками: упорядочивание руки карт
Сортировка вставками имитирует сортировку карт в руке: возьмите следующую карту (элемент) и вставьте её в правильную позицию среди уже отсортированных карт слева. Инвариант состоит в том, что arr[0:i] всегда отсортирован. Для каждого нового элемента сдвигайте большие элементы вправо, освобождая место. Этот алгоритм выполняется на месте, является устойчивым и имеет сложность O(n²) в худшем случае, но O(n) в лучшем случае для почти отсортированных данных.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Сортировка вставками пошагово
Проследим работу сортировки вставками на [3, 1, 4, 2]: i=1, key=1, сдвигаем 3 вправо → [1, 3, 4, 2]. i=2, key=4, сдвигов нет → массив не меняется. i=3, key=2, сдвигаем 4, затем 3 вправо → [1, 2, 3, 4]. Каждый элемент сравнивается с элементами слева от него, пока не будет найдена правильная позиция. Внутренний цикл while выполняет сдвиги с помощью присваиваний (это быстрее обменов, поскольку для одного сдвига требуется одно присваивание, а для обмена — три).
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Сортировка вставками для почти отсортированных данных
Главное преимущество сортировки вставками — сложность O(n + инверсии). Инверсия — это пара (i,j), для которой i < j, но arr[i] > arr[j]. Для почти отсортированных массивов, содержащих всего несколько инверсий, сортировка вставками чрезвычайно быстра — иногда на практике быстрее сортировки слиянием благодаря простоте и эффективному обращению к кэшу. Python использует сортировку вставками для небольших подмассивов в Timsort именно по этой причине.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Устойчивость при сортировке
Алгоритм сортировки является устойчивым, если равные элементы после сортировки сохраняют свой исходный взаимный порядок. Сортировка пузырьком и сортировка вставками устойчивы — они никогда не меняют местами равные элементы. Устойчивость важна при последовательной сортировке по нескольким ключам: сначала устойчиво отсортируйте по вторичному ключу, затем устойчиво отсортируйте по первичному, чтобы сохранить порядок по вторичному ключу среди элементов с одинаковым первичным ключом. Сортировка слиянием также устойчива, а пирамидальная и быстрая сортировки обычно нет.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableСортировка вставками как двоичный поиск
Внутренний цикл сортировки вставками одновременно находит правильную позицию и сдвигает элементы. Можно использовать двоичный поиск, чтобы найти позицию за O(log i) сравнений, но сдвиги по-прежнему занимают O(i) времени — поэтому общая сложность остаётся O(n²). Эта оптимизация уменьшает количество сравнений (что полезно для дорогостоящих функций сравнения), но не общее число операций. Такая «сортировка вставками с двоичным поиском» используется в Timsort для небольших размеров фрагментов.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Пузырьковая сортировка и сортировка вставками: когда что использовать
На собеседовании уверенно сформулируйте это сравнение: сортировка вставками однозначно лучше сортировки пузырьком — обе имеют сложность O(n²) в худшем случае и используют O(1) памяти, но сортировка вставками выполняет меньше записей (O(n+k) для k инверсий против O(n²) у сортировки пузырьком), лучше работает с кэшем и является практичным выбором для небольших n (её использует Timsort). Единственное реальное преимущество сортировки пузырьком — простота для обучения. В производственном коде всегда используйте встроенную сортировку языка.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Подсчёт инверсий как метрика
Количество инверсий в массиве равно числу пар (i,j), для которых i < j, но arr[i] > arr[j]. Сортировка вставками выполняет ровно столько сдвигов, сколько имеется инверсий, — это полезное наблюдение. Эффективный подсчёт инверсий (за O(n log n)) требует модифицированной сортировки слиянием. В качестве дополнительного вопроса при обсуждении сортировки интервьюеры иногда спрашивают: «Насколько ваш алгоритм учитывает инверсии?»
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedБыстрая проверка
Проверьте своё понимание понятий «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали: сортировка пузырьком выполняет n-1 проходов, на каждом из которых текущий максимум перемещается на своё окончательное место; сложность в худшем случае равна O(n²), а с флагом досрочного завершения в лучшем случае — O(n), сортировка вставками сдвигает элементы вправо, чтобы вставить текущий ключ в правильную отсортированную позицию, и работает за O(n + инверсии), что делает её оптимальной для почти отсортированных данных, а оба алгоритма устойчивы, используют O(1) памяти и имеют сложность O(n²) в худшем случае — но во всех практических сценариях сортировка вставками однозначно предпочтительнее сортировки пузырьком. Далее мы реализуем сортировку слиянием с нуля.
Часто задаваемые вопросы
Урок «Сортировка пузырьком и сортировка вставками» бесплатный?
Да — полный текст урока «Сортировка пузырьком и сортировка вставками» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Сортировка пузырьком и сортировка вставками»?
Напишите оба алгоритма квадратичной сортировки, поймите, почему они имеют сложность O(n²), и узнайте об единственном случае, когда сортировка вставками превосходит сортировку слиянием Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Сортировка пузырьком и сортировка вставками»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка пузырьком и сортировка вставками
- Сортировка слиянием: разделить, отсортировать, объединить
- Быстрая сортировка и выбор опорного элемента
- Сортировки без сравнений и sort() в Python