Как извлечь алгоритм из этих инструкций?

Question

Я читал "Искусство компьютерного программирования", и хотя в нем есть моменты высшей математики, которые я просто не могу получить, некоторые упражнения были забавными.

После того, как я выполнил одно из них, я перехожу к ответу, чтобы увидеть, сделал ли я лучше или хуже, чем то, что предлагает книга (обычно хуже), но я не понимаю, какой ответ для текущего, на котором я сейчас нахожусь, пытаясь передать вообще.

Вопрос о книге и предлагаемое решение можно найти здесь

Я понял, что t может быть количеством "пропущенных" элементов или может быть общей константой, но я действительно не понимаю, казалось бы, произвольной инструкции сортировать их по их компонентам, что для меня выглядит как вращение ваших колес с самого начала взгляд это не приближает вас к первоначальному порядку. И решение (среди прочего) заменить одну часть парных имен числом (файл G содержит все пары (i,xi) для n−t

Итак, мой вопрос прост: как мне извлечь алгоритм из этого ответа?

Немного уточнения:

Я понимаю, что он намеревается сделать, и как я перейду на его перевод на С ++. Что я не понимаю, так это то, почему я должен сортировать копии входного файла, и если да, то по каким критериям я сортирую, а также причины изменения одной стороны пар на число.

Answer 1

Предполагается, что имена можно сортировать и что для решения проблемы достаточно ленточных накопителей. Определите пару как (name, next_name), где next_name - это имя человека на западе. Копия файла пар производится на другую ленту. Первый файл отсортирован по имени, второй файл отсортирован по следующему имени. Ленточные сортировки - это сортировка по принципу слияния снизу вверх или более сложный вариант, называемый многофазной сортировкой слиянием, но для этой проблемы достаточно стандартной стандартной сортировки слияния снизу вверх. Для C++ вы могли бы использовать std::stable_sort() для эмуляции сортировки на ленте, используя лямбда-функцию для сравнения, сортировку по имени для первого файла и сортировку по next_name для второго файла.

Терминология для индексирования использует имя [1] для представления самого восточного имени и имя [n] для представления самого западного имени.

После первоначальной сортировки двух файлов пар решение заявляет, что "передача по файлам" выполняется для идентификации следующей за фамилией имени [n-1], но не указывает, каким образом. В процессе я предполагаю, что имя [n] также идентифицировано. Файлы сравниваются последовательно, сравнивая имя из первого файла с именем next_name из второго файла. Несовпадение указывает либо имя, имя [1], либо фамилию, имя [n], либо, в редких случаях, обе, и следующие пары из каждого файла должны быть проверены, чтобы определить, что указывает несоответствие. Когда идентифицируется фамилия, имя [n], имя из второй пары файлов будет следующим за фамилией, имя [n-1].

Когда имя [n-1] и имя [n] известны, выполняется операция слияния, использующая оба файла, пропуская имя [n-1] и имя [n], чтобы создать F с парами (name[i], name[i+2]) для i = 1 - n-2 (в порядке имен) и G с двумя парами (n-1, x[n-1]) и (n, x[n])) также в именах порядок (G и G'в порядке имен до последнего шага).

F копируется в H, и итерационный процесс выполняется, как описано в алгоритме, с удваиванием t каждый раз, 2, 4, 8, ... . После каждого прохода F'содержит пары (x[i], x[i+t]) для i = 1 до nt, затем G' сортируется и объединяется с G обратно в G', в результате чего G' содержит пары (i, x[i]) для i = nt к n, в порядке имен. В конце концов все пары заканчиваются в G (i, x[i]) для i = 1 до n в порядке имен, а затем G сортируется по индексу (левая часть пары), в результате чего имена сортируются в порядке.