lab03 — сортировки и подсчёт перестановок¶
Массив из 10 случайных чисел и три классические сортировки сравнением — выбором, вставками и пузырьковая. Каждая возвращает не только отсортированный массив, но и число выполненных перестановок, что позволяет сравнить алгоритмы по этому показателю. Поверх всего — текстовое меню.
Все функции сортировки работают по одному контракту: принимают список, не мутируют вход (копируют его через list(arr)) и возвращают кортеж (отсортированный_массив, число_перестановок).
Массив, печать и минимум¶
generate_array и print_array совпадают с lab01: массив заполняется random.randint(1, 100), печать идёт по индексам через собственную array_length (без встроенных len/range).
def get_min_element(arr: list[int]) -> int:
m = arr[0]
x = 1
while x < array_length(arr):
if arr[x] < m:
m = arr[x]
x += 1
return m
Это зеркало custom_max из lab01, только сравнение перевёрнуто (< вместо >). Сложность — O(n), один проход.
get_index_min_element — индекс минимума с произвольного места¶
Чтобы переиспользовать поиск минимума в сортировке выбором, функция возвращает индекс (а не значение) и принимает параметр start — позицию, с которой начинать поиск:
def get_index_min_element(arr: list[int], start: int = 0) -> int:
idx = start
x = start + 1
while x < array_length(arr):
if arr[x] < arr[idx]:
idx = x
x += 1
return idx
При start=0 это поиск минимума всего массива; при start=i — минимума в хвосте arr[i:], что и нужно сортировке выбором.
Сортировка выбором¶
Идея: массив делится на отсортированную левую часть и неотсортированный хвост. На каждом шаге находим минимум хвоста и ставим его в начало хвоста (меняем местами).
def selection_sort(arr: list[int]) -> tuple[list[int], int]:
result = list(arr)
swaps = 0
n = array_length(result)
i = 0
while i < n - 1:
min_idx = i
j = i + 1
while j < n:
if result[j] < result[min_idx]:
min_idx = j
j += 1
if min_idx != i:
result[i], result[min_idx] = result[min_idx], result[i]
swaps += 1
i += 1
return result, swaps
Перестановка засчитывается только когда минимум хвоста не на своём месте (min_idx != i). Поэтому число перестановок ≤ n−1 — это главная особенность алгоритма: он делает минимум обменов среди трёх, но всегда ~n²/2 сравнений независимо от данных.
selection_sort_with_min — та же логика, но внутренний поиск минимума заменён вызовом get_index_min_element(result, i) (задание 3). Результат и счётчик перестановок у двух вариантов совпадают.
Сортировка вставками¶
Идея: берём очередной элемент key и «вставляем» его в уже отсортированную левую часть, сдвигая вправо все элементы, что больше него.
def insertion_sort(arr: list[int]) -> tuple[list[int], int]:
result = list(arr)
swaps = 0
n = array_length(result)
i = 1
while i < n:
key = result[i]
j = i - 1
while j >= 0 and result[j] > key:
result[j + 1] = result[j] # сдвиг вправо
swaps += 1
j -= 1
result[j + 1] = key
i += 1
return result, swaps
Здесь перестановка — это каждый сдвиг элемента вправо. На почти отсортированных данных сдвигов мало (в пределе 0 — лучший случай O(n)), на обратно отсортированных — максимум.
Пузырьковая сортировка¶
Идея: многократно проходим по массиву, меняя местами соседей, если они стоят не по порядку. После каждого прохода очередной максимум «всплывает» в конец.
def bubble_sort(arr: list[int]) -> tuple[list[int], int]:
result = list(arr)
swaps = 0
n = array_length(result)
i = 0
while i < n - 1:
swapped = False
j = 0
while j < n - i - 1:
if result[j] > result[j + 1]:
result[j], result[j + 1] = result[j + 1], result[j]
swaps += 1
swapped = True
j += 1
if not swapped: # за проход ничего не меняли — массив уже отсортирован
break
i += 1
return result, swaps
Флаг swapped даёт ранний выход: на уже отсортированном массиве алгоритм делает один проход без обменов и завершается (лучший случай O(n)). В худшем случае (обратно отсортированный массив) число перестановок равно n·(n−1)/2.
Быстрая сортировка¶
Идея: выбираем опорный элемент (pivot), за один проход разбиваем массив на «меньше опорного» слева и «больше опорного» справа (схема Ломуто), ставим опорный на его финальное место и рекурсивно сортируем обе половины. В отличие от трёх предыдущих, это сортировка типа «разделяй и властвуй» со средней сложностью O(n·log n).
def quick_sort(arr: list[int]) -> tuple[list[int], int]:
result = list(arr)
def partition(low: int, high: int) -> tuple[int, int]:
pivot = result[high] # опорный — последний элемент отрезка
swaps = 0
i = low - 1 # граница части «меньше опорного»
j = low
while j < high:
if result[j] <= pivot:
i += 1
if i != j:
result[i], result[j] = result[j], result[i]
swaps += 1
j += 1
if i + 1 != high:
result[i + 1], result[high] = result[high], result[i + 1]
swaps += 1
return i + 1, swaps # позиция опорного и число обменов
def sort(low: int, high: int) -> int:
if low >= high:
return 0
pivot_idx, swaps = partition(low, high)
swaps += sort(low, pivot_idx - 1)
swaps += sort(pivot_idx + 1, high)
return swaps
total_swaps = sort(0, array_length(result) - 1)
return result, total_swaps
Сортировка работает рекурсивно по индексам low..high над копией входа. partition возвращает не только финальную позицию опорного, но и число обменов на этом шаге; sort суммирует обмены своего разбиения и обеих рекурсивных половин. Обмен засчитывается только при реальной перестановке (i != j и i + 1 != high), как и в selection_sort.
Перестановка здесь — обмен внутри partition. На случайных данных их заметно меньше, чем у квадратичных сортировок, но в худшем случае (уже отсортированный массив с опорным на краю) разбиения вырождаются и алгоритм деградирует до O(n²).
Подсчёт и сравнение перестановок¶
compare_swaps прогоняет один и тот же массив через все три алгоритма и собирает счётчики в словарь; print_comparison печатает их и называет победителя:
def compare_swaps(arr: list[int]) -> dict[str, int]:
return {
"Сортировка выбором": selection_sort(arr)[1],
"Сортировка вставками": insertion_sort(arr)[1],
"Пузырьковая сортировка": bubble_sort(arr)[1],
"Быстрая сортировка": quick_sort(arr)[1],
}
Вывод об эффективности:
- Сортировка выбором делает не больше n−1 перестановок, но максимум сравнений всегда. Выгодна, когда обмен элементов «дорогой», а сравнение «дешёвое».
- Сортировка вставками и пузырёк чувствительны к исходному порядку: на почти отсортированных данных они близки к O(n), на обратно отсортированных вырождаются в максимум перестановок (n·(n−1)/2 у пузырька).
- По времени первые три — O(n²) в среднем и худшем случае. Быстрая сортировка в среднем O(n·log n) и на больших массивах обгоняет квадратичные, но в худшем случае тоже деградирует до O(n²). «Перестановки» — лишь один из показателей; полная картина включает ещё и число сравнений.
Меню¶
menu генерирует массив, печатает его и минимум, затем в цикле читает выбор пользователя через input():
| Пункт | Действие |
|---|---|
| 1 | Сортировка выбором |
| 2 | Сортировка выбором через get_index_min_element |
| 3 | Сортировка вставками |
| 4 | Пузырьковая сортировка |
| 5 | Быстрая сортировка |
| 6 | Сравнить все алгоритмы по перестановкам |
| 7 | Сгенерировать новый массив |
| 0 | Выход |
Массив хранится между итерациями, поэтому пункты 1–6 работают над одними и теми же данными — сравнение перестановок честное. Пункт 7 заменяет массив новым.
Где это в проде¶
Свои сортировки в проде не пишут — но понимание, как они устроены, объясняет поведение стандартных:
- Стандартные сортировки — гибриды этих идей.
sorted()/list.sort()в Python иArrays.sort()в Java используют Timsort: сортировку вставками на коротких и почти отсортированных участках (где она близка к O(n)) плюс слияние.slices.Sortв Go — pdqsort: быстрая сортировка с защитой от худшего случая (переключение на heapsort при деградации). Ровно те свойства, что видно в лабе: вставки выгодны на почти готовых данных, quicksort быстра в среднем, но опасна в худшем. - Сортировка в инструментах эксплуатации.
sort -k2 -nпо логам,ORDER BYв БД (без подходящего индекса это сортировка в памяти или на диске —external mergeв плане запроса, заметная статья расхода ресурсов). Для «top-N самых тяжёлых запросов» полная сортировка избыточна — там выгоднее куча (lab07). - Стабильность важна. Стабильная сортировка не переставляет равные элементы — это то, что позволяет сортировать по нескольким ключам последовательно (сначала по времени, потом по сервису). Timsort стабилен;
slices.Sort— нет (для стабильной в Go естьslices.SortStableFunc).
Параллельная реализация на Go¶
Все четыре сортировки со счётчиком перестановок реализованы на Go в пакете src/golang/dsa/lab03. Каждая возвращает новый отсортированный срез и число перестановок, не мутируя вход; семантика подсчёта перестановок совпадает с Python (table-driven тесты проверяют это на отсортированном и обратно отсортированном входах). Пример — сортировка вставками.