СВ в 19:26, 25 октября 2026

2026-10-25T19:26:38Z

← Предыдущая		Версия 19:26, 25 октября 2026
Строка 1:		Строка 1:
	== TL;DR ==		== TL;DR ==

	'''Timsort''' — гибридная '''устойчивая''' сортировка, придуманная Тимом Петерсом в 2002 году для Python и ставшая стандартом в Java, Android и движках JavaScript. Идея: реальные данные почти всегда содержат '''уже упорядоченные серии''' (runs). Timsort находит их, короткие серии удлиняет до '''minrun''' (≈32–64) бинарной сортировкой вставками, а затем сливает runs по специальной '''политике''', поддерживающей инвариант в духе чисел Фибоначчи. Это даёт: лучший случай <math>O(n)</math> (на почти отсортированных данных), средний и '''худший''' <math>O(n\log n)</math>, '''устойчивость''' и '''адаптивность''', ценой до <math>O(n)</math> дополнительной памяти под буфер слияния. Ускорение слияний даёт '''режим галопирования''' — вместо поэлементных сравнений копируются целые блоки после экспоненциального и бинарного поиска.		'''Timsort''' — гибридная '''устойчивая''' сортировка, придуманная Тимом Петерсом в 2002 году для Python и ставшая стандартом в Java, Android и движках JavaScript. Идея: реальные данные почти всегда содержат '''уже упорядоченные серии''' (runs). Timsort находит их, короткие серии удлиняет до '''minrun''' (≈32–64) бинарной сортировкой вставками, а затем сливает runs по специальной '''политике''', поддерживающей инвариант в духе чисел Фибоначчи. Это даёт: лучший случай <math>O(n)</math> (на почти отсортированных данных), средний и '''худший''' <math>O(n\log n)</math>, '''устойчивость''' и '''адаптивность''', ценой до <math>O(n)</math> дополнительной памяти под буфер слияния. Ускорение слияний даёт '''режим галопирования''' — вместо поэлементных сравнений копируются целые блоки после экспоненциального и бинарного поиска. Лучший обзор «куда встроен Timsort» — рис. 7; сравнение с классическими сортировками — в [[Быстрая сортировка]] и [[Пирамидальная сортировка]].

	{\| class="wikitable"		{\| class="wikitable"
Строка 36:		Строка 36:
	'''Устойчивость (stability).''' Равные элементы сохраняют исходный взаимный порядок. Timsort устойчив: строго убывающий run разворачивается, а равные элементы «убывания» не образуют и не переворачиваются; при слиянии из двух равных выбирается левый.		'''Устойчивость (stability).''' Равные элементы сохраняют исходный взаимный порядок. Timsort устойчив: строго убывающий run разворачивается, а равные элементы «убывания» не образуют и не переворачиваются; при слиянии из двух равных выбирается левый.

	'''Политика слияний (merge policy).''' Runs хранятся на '''стеке'''; после добавления нового run проверяется '''инвариант''', и при его нарушении часть runs сливается. Инвариант: для верхних трёх runs <math>X, Y, Z</math> (~~снизу вверх~~) должны выполняться <math>Z > Y + X</math> и <math>Y > X</math>.		'''Политика слияний (merge policy).''' Runs хранятся на '''стеке'''; после добавления нового run проверяется '''инвариант''', и при его нарушении часть runs сливается. Инвариант: для верхних трёх runs <math>X, Y, Z</math> (X — верх, Y — середина, Z — низ) должны выполняться <math>Z > Y + X</math> и <math>Y > X</math>.

	'''Галопирование (galloping).''' Если при слиянии одна сторона выигрывает много раз подряд, вместо поэлементного сравнения выполняют экспоненциальный, затем бинарный поиск и копируют сразу блок.		'''Галопирование (galloping).''' Если при слиянии одна сторона выигрывает много раз подряд, вместо поэлементного сравнения выполняют экспоненциальный, затем бинарный поиск и копируют сразу блок.
Строка 149:		Строка 149:
	</syntaxhighlight>		</syntaxhighlight>

	'''Разбор.''' Если на стеке длины <code>10, 25, 40</code> (сверху <code>10</code>), то <math>10 \le ~~25 + 40~~</math> ~~— инвариант нарушен~~, сливаем (см. рис. 4).		'''Разбор.''' Если на стеке длины <code>10, 25, 30</code> (сверху <code>10</code>), то <math>Y > X</math> выполнено (<math>25 > 10</math>), а <math>Z > Y + X</math> нарушено (<math>30 \le 35</math>). Сливаем <code>Y</code> и <code>X</code>: получаем run длиной 35. Теперь для двух runs <math>30 > 35</math> неверно, поэтому сливаем всё в один run длиной 65 (см. рис. 4).

	'''Смысл.''' Инвариант заставляет длины runs расти хотя бы как числа Фибоначчи, поэтому их не больше <math>O(\log n)</math> и каждый элемент участвует в <math>O(\log n)</math> слияниях → <math>O(n\log n)</math>.		'''Смысл.''' Инвариант заставляет длины runs расти хотя бы как числа Фибоначчи, поэтому их не больше <math>O(\log n)</math> и каждый элемент участвует в <math>O(\log n)</math> слияниях → <math>O(n\log n)</math>.
Строка 187:		Строка 187:
	</syntaxhighlight>		</syntaxhighlight>

	'''Разбор.''' На рис. 5 правый run <code>[5,9,12,17,40]</code>, левый элемент <code>18</code>; ~~после серии побед правого~~ сторона ~~галопирует~~: находит, что <code>5,9,12,17 < 18</code>, и копирует их блоком.		'''Разбор.''' На рис. 5 правый run <code>[5,6,7,8,9,10,11,40]</code>, левый элемент <code>18</code>; правая сторона выигрывает 7 раз подряд, включается галопирование: Timsort находит, что <code>5,6,7,8,9,10,11 < 18</code>, и копирует их блоком.

	'''Сложность.''' Слияние <math>O(len_1 + len_2)</math>; галопирование уменьшает число '''сравнений''' до <math>O(\log k)</math> на блок, что важно при дорогих сравнениях (объекты, строки).		'''Сложность.''' Слияние <math>O(len_1 + len_2)</math>; галопирование уменьшает число '''сравнений''' до <math>O(\log k)</math> на блок, что важно при дорогих сравнениях (объекты, строки).
Строка 228:		Строка 228:
	\| 2 \|\| 3 < minrun → удлиняем до 4, бинарные вставки по <code>[3,5,9,8]</code> \|\| run <code>[3,5,8,9]</code>		\| 2 \|\| 3 < minrun → удлиняем до 4, бинарные вставки по <code>[3,5,9,8]</code> \|\| run <code>[3,5,8,9]</code>
	\|-		\|-
	\| 3 \|\| Поиск run от 4: <code>7,4</code> — строго убывающий (длина 2) → разворот \|\| run <code>[4,7]</code>		\| 3 \|\| Поиск run от 4: <code>7,4,1</code> — строго убывающий (длина 3) → разворот \|\| run <code>[1,4,7]</code>
	\|-		\|-
	\| 4 \|\| 2 < minrun → удлиняем до 4, сортируем <code>[4,7,1,2]</code> \|\| run <code>[1,2,4,7]</code>		\| 4 \|\| 2 < minrun → удлиняем до 4, сортируем <code>[1,4,7,2]</code> \|\| run <code>[1,2,4,7]</code>
	\|-		\|-
	\| 5 \|\| Поиск run от 8: <code>6,10</code> — возрастающий \|\| run <code>[6,10]</code>		\| 5 \|\| Поиск run от 8: <code>6,10</code> — возрастающий \|\| run <code>[6,10]</code>
Строка 349:		Строка 349:
	* [[Асимптотическая сложность]] — оценки и адаптивность.		* [[Асимптотическая сложность]] — оценки и адаптивность.
	* [[Дерево отрезков]] — другая структура «разделяй и властвуй».		* [[Дерево отрезков]] — другая структура «разделяй и властвуй».


	== Источники ==		== Источники ==

СВ: Новая страница: «== TL;DR == '''Timsort''' — гибридная '''устойчивая''' сортировка, придуманная Тимом Петерсом в 2002 го...»

2026-10-07T18:58:00Z

Новая страница: «== TL;DR == '''Timsort''' — гибридная '''устойчивая''' сортировка, придуманная Тимом Петерсом в 2002 го...»

Внесённые изменения

Timsort - История изменений

СВ в 19:26, 25 октября 2026

СВ: Новая страница: «== TL;DR == '''Timsort''' — гибридная '''устойчивая''' сортировка, придуманная Тимом Петерсом в 2002 го...»