4511
правок
Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 22:14, 18 апреля 2023
, 18 апреля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
'''Задача 1 (Внешняя сортировка)''' | '''Задача 1 (Внешняя сортировка)''' | ||
Дано: записи входных данных | Дано: записи входных данных <math>R_0, R_1, R_2, ...</math> изначально распределены в виде чередующихся полос по D дискам в виде блоков, так что запись <math>R_i</math> находится в блоке <math>\lfloor i/B \rfloor</math>, а блок ј хранится на диске j mod D. | ||
Требуется: найти чередующееся представление | Требуется: найти чередующееся представление перестановочного упорядочения <math>R_{\sigma(0)}, R_{\sigma(1)}, R_{\sigma(2)}, ...</math> входных записей, обладающее следующим свойством: <math>key(R_{\sigma(i)}) \le key(R_{\sigma(i + 1)})</math> для всех <math>i \ge 0</math>. | ||
| Строка 39: | Строка 39: | ||
Задача 2 (Перестановка) | '''Задача 2 (Перестановка)''' | ||
Дано: те же исходные предположения, что и в задаче внешней сортировки. Кроме того, задана перестановка | Дано: те же исходные предположения, что и в задаче внешней сортировки. Кроме того, задана перестановка <math>\sigma</math> целых чисел {0, 1, 2, ... N — 1}. | ||
Требуется: найти чередующееся представление | Требуется: найти чередующееся представление перестановочного упорядочения <math>R_{\sigma(0)}, R_{\sigma(1)}, R_{\sigma(2)}, ...</math> входных записей. | ||
== Основные результаты == | == Основные результаты == | ||