39
правок
Изменения
Timsort
,Нет описания правки
* Все элементы оставшегося массива добавляются в конец нового массива.
===Пример===
Возьмем <tex>n = 356</tex>. При таком <tex>n</tex> <tex>minrun</tex> оказался равным 45. Ниже представлена работа алгоритма.
Число с волной показывает шаг, на котором произошло сливание нижестоящих подмассивов.
Рассмотрим процедуру слияния двух массивов:
== Доказательство времени работы алгоритма ==
Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод '''Galloping Mode'''. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.Пусть <tex>k</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex> k </tex> = <tex dpi=150> \ulcorner \frac{n}{minrun} \urcorner </tex>. Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>О(nlog(n))</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длинну. То есть Можно сказать больше {{---}} пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длинны (данный факт хорошо виден на примере). Безусловно, после разбения массива на блоки длинной <tex>run_1minrun</tex>последний блок может быть отличен от данного значения практически в 2 раза, но эти 20-30 элементов разницы при <tex>run_2n</tex> такиепорядка <tex>10^6</tex> практически не повлияют на время работы. Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается <tex>run_1.size \gg run_2approx</tex> 2 раза.sizeТаким образом получаем, что каждый подмассив <tex>run_i</tex> будут слиты только тогда, когда размеры соответствующих подмассивовможет участвовать в не более <tex>O(log(n))</tex> операций слияния, а значит и каждый элемент будет задействован в которые они войдут будут примерно равнысравниниях не более <tex>O(log(n))</tex> раз. Например, если на вход подан массив Элементов <tex>64, 32, 16, 8, 4, 2, 1n</tex>, то, временно забыв про понятие откуда получаем оценку в <tex>minrunO(nlog(n))</tex>, '''Timsort''' сделает следующие слияния:# 64, 32, 16, 8, 4, 2, 1, 1# 64, 32, 16, 8, 4, 2, 2# 64, 32, 16, 8, 4, 4# 64, 32, 16, 8, 8# 64, 32, 16, 16# 64, 32, 32# 64, 64# 128.
== Источники ==