Учебный кейс: эмпирическое сравнение quicksort, mergesort и timsort
1) Цель
- Показать поведение алгоритмов на трёх типах входных данных (лучший, худший, реальный).
- Замерить время выполнения и объяснить наблюдаемые различия.
- Рассказать, когда каждый алгоритм предпочтителен.
2) Наборы данных (генерация)
- Параметры: размер массива $n$ (примерные значения для тестов: $n\in \{10^3,10^4,10^5\}$).
- Best (для timsort/mergesort): уже отсортированный массив: $A=[1,2,\dots ,n]$.
- Worst (для детерминированного quicksort с последним/первым элементом в качестве опоры): отсортированный массив в порядке, вызывающем деградацию: $A=[1,2,\dots ,n]$ (или обратный порядок — в зависимости от реализации опоры).
- Realistic (реальный): частично упорядоченный массив, например, конкатенация $k$ отсортированных блоков длины $r$ с последующей случайной перестановкой блоков; формально: разбить упорядоченную последовательность на блоки длины $r$ и перемешать блоки. Это моделирует данные с длинными «run»-ами, характерными для реальных данных.
3) Реализация (Python, воспроизводимо)
- Детская, наглядная реализация детерминированного quicksort (опора = последний элемент), mergesort, и timsort — стандартный Python sort (timsort). Для честности считать замеры времени функцией time.perf_counter, запускать несколько прогонов и брать медиану.
Примерный код (упрощённо, без лишних объяснений):
```
import random, time
def gen_sorted(n): return list(range(n))
def gen_worst_quick(n): return list(range(n)) # вызывает O(n^2) у простого quicksort
def gen_realistic(n, run=100):
# создаём отсортированные блоки длиной run и перемешиваем блоки
blocks = [list(range(i, min(n, i+run))) for i in range(0,n,run)]
random.shuffle(blocks)
out=[]
for b in blocks: out.extend(b)
return out
def quicksort(a):
if len(a)<=1: return a
pivot = a[-1] # детерминированный выбор — демонстрация худшего случая
L=[x for x in a))
def merge(l,r):
i=j=0; out=[]
while i<len(l) and j<len(r):
if l[i]<=r[j]:
out.append(l[i]); i+=1
else:
out.append(r[j]); j+=1
out.extend(l[i:]); out.extend(r[j:]); return out
def timsort(a):
b = list(a)
b.sort()
return b
def bench(func, arr, repeats=5):
times=[]
for _ in range(repeats):
a = list(arr)
t0=time.perf_counter()
func(a)
t1=time.perf_counter()
times.append(t1-t0)
times.sort()
return times[len(times)//2] # медиана
```
Протокол запуска:
- Для каждого $n$ и набора данных (best, worst, real) сгенерировать массив, выполнить каждую сортировку $R$ раз (например $R=5$), взять медианное время.
- Выключить другие нагружающие процессы, фиксировать среду (одна машина, одинаковый язык и реализация).
- Для quicksort можно дополнительно реализовать randomized pivot, чтобы увидеть разницу.
4) Ожидаемые результаты (качественно и в относительных величинах)
- Сложности:
- Quicksort (детерм., pivot = крайний): среднее $O(n\log n)$, худшее $O(n^2)$.
- Mergesort: всегда $O(n\log n)$, дополнительная память $O(n)$.
- Timsort: адаптивный, в среднем/на практике $O(n\log n)$, на уже отсортированных данных близок к $O(n)$ благодаря обнаружению run-ов; стабильный.
Все в виде KaTeX: quicksort — $O(n\log n)$ в среднем, $O(n^2)$ в худшем; mergesort — $O(n\log n)$ всегда; timsort — адаптивный, в лучшем случае примерно $O(n)$, в худшем $O(n\log n)$.
- Пример относительных результатов (нормализуем к mergesort = $1.0$ для одной конкретной машины и одного $n$; реальные числа зависят от реализации и железа):
- Для случайных данных (real/random):
- quicksort ≈ $0.9-1.2$ (быстр/медл по сравнению с mergesort)
- mergesort = $1.0$ - timsort ≈ $0.8-1.0$ - Для уже отсортированных данных (best для timsort, плохой для детерм. quicksort):
- quicksort (детерм.) ≫ $n\log n$, возможен рост времени до порядка $n^2$ (например, в относительных единицах ≈ $10-100$ раз медленнее)
- mergesort ≈ $1.0$ - timsort ≪ $1.0$ (может быть существенно быстрее, близко к линейному)
- Для realistic (частично упорядоченные, с длинными run-ами):
- timsort часто выигрывает (за счёт использования run-ов) — может дать прирост в несколько раз по сравнению с mergesort/quicksort.
- mergesort стабильна и предсказуема (~$1.0$).
- детермин. quicksort может быть чуть хуже из-за плохого разбиения; randomized quicksort вернёт средние показатели.
5) Объяснение наблюдений (коротко)
- Почему quicksort быстрый обычно: хороший баланс разбиений даёт малую константу и низкое использование памяти (рекурсия $O(\log n)$), поэтому в среднем он эффективен.
- Почему mergesort устойчив: всегда $O(n\log n)$ с предсказуемой производительностью; нуждается в дополнительной памяти $O(n)$; хорош для внешней сортировки и когда нужна стабильность.
- Почему timsort выигрывает на реальных данных: он обнаруживает уже существующие отсортированные «run»-ы и объединяет их; если данных много «локальных упорядоченностей», timsort может вести себя почти линейно.
- Худший случай у детерминированного quicksort: если опора выбирается плохо (крайний элемент) и вход уже отсортирован, разбиение вырождается, глубина рекурсии ≈ $n$ и суммарная работа ≈ $O(n^2)$.
- Потребление памяти: quicksort (in-place) — $O(\log n)$ стек (в среднем), mergesort — $O(n)$ буфер, timsort — использует дополнительные буферы и стек ран; в худшем случае память может быть порядка $O(n)$, но на практике обычно меньше.
6) Рекомендации: когда что выбирать
- Timsort (стандартный Python sort): предпочтителен для общих практических задач, особенно на частично упорядоченных реальных данных.
- Randomized quicksort (или quicksort с медианой из трёх): хорош для in-memory сортировки, низкая константа и малая дополнительная память; использовать randomized pivot, чтобы избегать худших случаев.
- Mergesort: выбирать, если важна стабильность и предсказуемое поведение, либо при внешней сортировке/распределённой сортировке, когда требуется гарантированное $O(n\log n)$.
7) Дополнения для учебного задания
- Задание студентам: реализовать код выше, прогнать на трёх $n$, сравнить медианные времена, построить графики времени vs $n$ (log-log), измерить число сравнений/копирований (инструментировать код), показать влияние выбора опоры в quicksort (последний элемент vs случайный vs медиана из трёх).
- Интерпретация: попросить объяснить наблюдаемые наклоны кривых и ответить на вопрос, при каких входах timsort даёт выигрыш > $2\times$ vs mergesort.
Если хотите, могу:
- прислать готовый исполняемый Python-скрипт для запуска и сбора данных с печатью таблиц,
- или подготовить шаблон отчёта с ожидаемыми графиками и местом для вставки результатов.