143
правки
Изменения
Нет описания правки
Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_i</tex>: в нашем случае, алгоритм работает за <tex>O(minrun + inv)</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>\mathtt{k}</tex> получим, что сортировка всех блоков может занять <tex>O(minrun + inv) \cdot k = O(minrun + inv) \cdot </tex><tex dpi=150>\left\lceil \frac{n}{minrun} \right\rceil </tex>. Что в худшем случае <tex dpi=150 >(inv = \frac{minrun(minrun - 1)}{2} )</tex> может занимать <tex>O(n \cdot minrun) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после эксперементов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>.
== Некорректность timsort в Java ==
Метод mergeCollapce <tex>\mathtt{mergeCollapse}</tex> (Java) - который сливает серии(<tex>\mathtt{runLen}</tex>) :
'''private void''' mergeCollapse() { //метод, содержащий ошибку
'''while''' (stackSize > 1) {
mergeAt(n);
} '''else''' {
}
}
}
В результате выполнения метода mergeCollapce<tex>\mathtt{mergeCollapse}</tex>, утверждается что для последних трех серий(runLen) выполняются следующие условия(инвариант):*<tex> runLen[n - 2] > runLen[n - 1] + runLen[n]</tex>*<tex>runLen[n - 1] > runLen[n]</tex>
Утверждается, что этого достаточно, но самом деле нет. Рассмотрим пример.
Пусть <tex>\mathtt{runLen }</tex> содержит следующий набор длин:
<tex> 23, 16, 5, 4, 6 </tex>
На первом шаге в цикле будут объединены серии : <tex>5 </tex> и <tex>4 </tex> (<tex>5 < 4 + 6</tex>, <tex>5 < 6</tex>). Получим:
<tex> 23, 16, 9, 6 </tex>
На втором шаге,в последней тройке устанавливается инвариант и <tex>\mathtt{mergeCollapse }</tex> завершает свою работу, но инвариант для всего массива не восстановлен: он нарушается в первой тройке, так как <tex>23 < 16 + 9</tex>.В результате нарушения инварианта, длины серий растут медленнее, чем ожидалось, в результате чего их кол-во превышает <tex>\mathtt{runLen.lengthLength}</tex>, что привод к <tex>\mathtt{ArrayOutOfBoundsException}</tex>.
Основная идея исправления ошибки {{---}} проверять, что инвариант соблюдается для четырёх последних серий в runLen вместо трёх.
'''if''' ( (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1])
|| (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {
== Источники информации==
* [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки Timsort]
* [http://habrahabr.ru/post/251751/ Habrahabr - Доказательство некорректности алгоритма сортировки Android, Java и Python]
==См. также==
* [[Сортировка кучей]]
