4551
правка
Сортировка без явного задания параметров кэша: различия между версиями
Материал из WEGA
Сортировка без явного задания параметров кэша (посмотреть исходный код)
Версия от 00:31, 12 марта 2017
, 12 марта 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
[[Файл:Sort_01.png]] | |||
Рис. 1. Общая рекурсия сортировки воронкой (слева) и 16-слияния (справа) | Рис. 1. Общая рекурсия сортировки воронкой (слева) и 16-слияния (справа) | ||
| Строка 40: | Строка 41: | ||
'''Неявная сортировка без явного задания параметров кэша''' | '''Неявная сортировка без явного задания параметров кэша''' | ||
Франческини в [7] показал, как неявно выполнить оптимальную сортировку без задания параметров кэша, используя только O(1) памяти – т.е. все данные хранятся во входном массиве,за исключением O(1) дополнительных слов с информацией. В частности, выходной массив является простой перестановкой входного. | Франческини в [7] показал, как неявно выполнить оптимальную сортировку без задания параметров кэша, используя только O(1) памяти – т.е. все данные хранятся во входном массиве, за исключением O(1) дополнительных слов с информацией. В частности, выходной массив является простой перестановкой входного. | ||
