39
правок
Изменения
Нет описания правки
<tex>*</tex> Все элементы оставшегося массива добавляются в конец нового массива.
===Модификация процедуры слияния подмассивов (Galloping Mode)===
Рассмотрим процедуру слияния двух массивов:
<tex>A = {1, 2, 3, ..., 9999, 10000}</tex>
<tex>B = {20000, 20001, 20002, ..., 29999, 30000}</tex>
Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копирований. Алгоритм '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''«галоп»'''. Алгоритм следующий:
<tex>*</tex> Начинается процедура слияния.
<tex>*</tex> На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.
<tex>*</tex> Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''«галопа»''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
<tex>*</tex> В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.
Для вышеописанных массивов <tex> A, B </tex> алгоритм выглядит следующим образом:
Первые 7 итераций сравниваются числа <tex>1, 2, 3, 4, 5, 6, 7</tex> из массива <tex>A</tex> с числом <tex>20000</tex>, так как <tex>20000</tex> больше, то элементы массива <tex>A</tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим '''«галопа»''': сравнивает с числом <tex>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^{i - 1}, ..., 10000 </tex> массива <tex>A</tex>. (<tex> \thicksim\log_{2}(n)</tex> сравнений). После того как конец массива <tex>A</tex> достигнут и известно, что он весь меньше <tex>B</tex>, нужные данные из массива <tex>A</tex> копируются в результирующий.
== Источники ==
