Сортировки без сравнений и sort() в Python
Изучите сортировку подсчётом и поразрядную сортировку целочисленных массивов и поймите, как внутри работает Timsort Python при вызовах встроенной sort
«Сортировки без сравнений и sort() в Python» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Нижняя граница O(n log n) для сравнений
Любой алгоритм сортировки, определяющий порядок только с помощью сравнений элементов, требует в худшем случае как минимум Ω(n log n) сравнений. Это доказывается с помощью дерева решений: для сортировки n элементов необходимо различать n! возможных порядков. Бинарному дереву решений (каждая вершина — сравнение) требуется как минимум log₂(n!) ≈ n log₂(n) уровней. Чтобы преодолеть эту границу, нужны дополнительные сведения о самих элементах — например, информация о том, что они являются целыми числами из ограниченного диапазона.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingСортировка подсчётом: сортировка по частоте
Сортировка подсчётом подсчитывает частоту каждого значения, а затем восстанавливает отсортированный массив по этим подсчётам. Для неё необходимо заранее знать диапазон значений [0, k). Временная сложность: O(n + k); сложность по памяти: O(k). При небольшом k относительно n (например, при сортировке возрастов от 0 до 120 или однозначных чисел) сортировка подсчётом превосходит все сортировки, основанные на сравнениях. При большом k затраты памяти O(k) делают её непрактичной.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Стабильная сортировка подсчётом с накопленными количествами
Для стабильной сортировки подсчётом (что важно при сортировке объектов по ключу) вычислите накопленные количества так, чтобы cum[v] указывало на начальную позицию значения v в выходном массиве. Просмотрите входной массив справа налево, помещая каждый элемент на позицию cum[key] - 1 и уменьшая это значение. Так получается стабильная сортировка — элементы с одинаковым ключом сохраняют исходный взаимный порядок.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Поразрядная сортировка: сортировка по разрядам
Поразрядная сортировка сортирует целые числа по одному разряду за раз — от младшего значащего разряда (LSD) к старшему (MSD), используя стабильную сортировку (например, сортировку подсчётом) на каждой позиции разряда. После d проходов (по одному на каждый разряд) массив полностью отсортирован. Временная сложность: O(d × (n + k)), где d = количество разрядов, а k = основание системы счисления (обычно 10). Для n целых чисел, ограниченных значением W, d = log_k(W), что даёт общую сложность O(n log_k(W)).
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Сортировка по корзинам: распределение по корзинам
Сортировка по корзинам распределяет элементы по фиксированному числу корзин на основе диапазона значений, сортирует каждую корзину (для небольших корзин — сортировкой вставками) и объединяет их. Для равномерно распределённых данных в [0, 1) n корзин дают среднее время O(n). Сложность: O(n + k) в среднем и O(n²) в худшем случае (если все элементы попали в одну корзину). Этот метод особенно полезен, когда распределение данных известно и приблизительно равномерно.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listВнутреннее устройство сортировки Тимсорт в Python
Встроенные в Python функции sorted() и list.sort() используют сортировку Тимсорт, разработанную Тимом Питерсом в 2002 году. Тимсорт — это гибрид сортировки слиянием и сортировки вставками. Алгоритм ищет «естественные серии» (уже отсортированные подпоследовательности) и использует сортировку вставками, чтобы наращивать серии длиной до 64 элементов. Затем он объединяет серии с помощью сортировки слиянием, применяя несколько оптимизаций: галопирование (массовый пропуск элементов, когда одна серия доминирует) и размещение серий в стеке.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Python: sort() и sorted(): ключевые различия
list.sort() сортирует список на месте, возвращает None и работает только со списками. sorted(iterable) работает с любым итерируемым объектом (кортежами, генераторами, словарями) и возвращает новый список. Обе функции принимают параметры key и reverse. Распространённая ошибка: присвоить результат lst.sort() переменной и удивляться, почему получается None. Всегда используйте sorted(), когда нужна отсортированная версия и требуется сохранить исходный объект.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Пользовательские ключи сортировки на собеседованиях
Метод сортировки Python принимает функцию key, которая вычисляется один раз для каждого элемента (в отличие от компаратора C, вызываемого для каждой пары). Распространённые ключи сортировки на собеседованиях: len для длины строки, lambda x: -x для сортировки по убыванию, lambda x: (x[1], x[0]) для сортировки по нескольким ключам и str.lower для сортировки без учёта регистра. Сортировка Python гарантированно стабильна, поэтому сортировка по нескольким ключам работает корректно.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Когда использовать каждый вид сортировки на собеседованиях
Выбирайте подходящую сортировку в зависимости от контекста:
- Используйте Python's sorted()/list.sort(): вариант по умолчанию для всех задач на собеседовании — Тимсорт оптимален
- Сортировка подсчётом: когда значения — небольшие целые числа из ограниченного диапазона (от 0 до k, где k мало)
- Поразрядная сортировка: когда нужно отсортировать много целых чисел с известной разрядностью или количеством цифр
- Сортировка по корзинам: когда данные представлены равномерно распределёнными вещественными числами из известного диапазона
- Реализуйте сортировку слиянием: когда требуется написать стабильную сортировку O(n log n) с нуля
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Сортировка без сортировки: k лучших элементов с помощью кучи
Во многих задачах на собеседованиях требуется получить результат, похожий на сортировку, без полной сортировки. Для поиска k лучших элементов мин-куча размера k работает за O(n log k) — быстрее, чем O(n log n), когда k << n. Для поиска k-го по величине элемента алгоритм быстрого выбора работает за O(n) в среднем. Для поиска медианы подход с двумя кучами работает за O(log n) на каждую вставку. Эти методы частичной сортировки стоит знать как более быстрые альтернативы полной сортировке.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Стабильность сортировки по нескольким ключам
Стабильность обеспечивает корректную сортировку по нескольким ключам: сначала стабильно отсортируйте данные по вторичному ключу, а затем стабильно — по первичному. При одинаковых значениях первичного ключа порядок по вторичному ключу сохраняется. Этот приём используется в базах данных (ORDER BY col1, col2) и в поразрядной сортировке (каждый проход по разряду должен быть стабильным, чтобы весь алгоритм работал корректно). Сортировка Python всегда стабильна, поэтому этот шаблон надёжен.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованиям по программированию» из этого урока.
Повторение урока
В этом уроке Вы узнали, что сортировки на основе сравнений ограничены снизу величиной O(n log n) — для преодоления этой границы нужна информация, не связанная со сравнениями, например ограниченные целые числа, что сортировка подсчётом достигает O(n + k), подсчитывая частоты, поразрядная сортировка обрабатывает разряды с общей сложностью O(d × (n + k)), а сортировка по корзинам использует равномерное распределение и работает за O(n) в среднем, а также что сортировка Тимсорт в Python — практический вариант по умолчанию: она стабильна, работает за O(n log n) в худшем случае, за O(n) в лучшем случае и быстрее любой реализации, написанной вручную, на реальных данных. Далее Вы освоите классический двоичный поиск.
Часто задаваемые вопросы
Урок «Сортировки без сравнений и sort() в Python» бесплатный?
Да — полный текст урока «Сортировки без сравнений и sort() в Python» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Сортировки без сравнений и sort() в Python»?
Изучите сортировку подсчётом и поразрядную сортировку целочисленных массивов и поймите, как внутри работает Timsort Python при вызовах встроенной sort Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Сортировки без сравнений и sort() в Python»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка пузырьком и сортировка вставками
- Сортировка слиянием: разделить, отсортировать, объединить
- Быстрая сортировка и выбор опорного элемента
- Сортировки без сравнений и sort() в Python