Содержание
- 2. Общие сведения Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002
- 3. Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе
- 4. По специальному алгоритму входной массив разделяется на подмассивы. Каждый подмассив сортируется сортировкой вставками. Отсортированные подмассивы собираются
- 5. Шаг 0. Вычисление minrun. оно не должно быть слишком большим, поскольку к подмассиву размера minrun будет
- 6. Шаг 1. Разбиение на подмассивы и их сортировка Указатель текущего элемента ставится в начало входного массива.
- 7. Шаг 2. Слияние Объединять подмассивы примерно равного размера Сохранить стабильность алгоритма — то есть не делать
- 8. Шаг 2.1 Слияние
- 9. Если одно из правил нарушается — массив Y сливается с меньшим из массивов X и Z.
- 10. Процедура слияния подмассивов Создается временный массив в размере меньшего из соединяемых подмассивов. Меньший из подмассивов копируется
- 11. Модификация процедуры слияния подмассивов (Galloping Mode) A = {1, 2, 3,..., 9999, 10000} B = {
- 12. Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из
- 13. Пример использования Galloping Mode A = {1, 2, 3,..., 9999, 10000} B = { 20000, 20001,
- 14. Оценка TimSort является одной из самых быстрых и удобных сортировок, в лучшем случае работая за время
- 16. Скачать презентацию