Обратное идеальное тасование выполняет обратную процедуру: мы попеременно откладываем карты в верхнюю и нижнюю половину колоды.

Программа 11.1 Идеальное тасование и обратное идеальное тасование

Функция shuffle переупорядочивает подмассив а[1], . . . , а[г] путем деления этого подмассива пополам, после чего попеременно берет элементы из каждой половины массива: элементы из первой половины переходят в позиции с четными номерами получающегося при этом массива, а элементы из второй половины переходят в позиции с нечетными номерами. Функция unshuffle выполняет обратную процедуру: элементы, занимающие четные позиции, переходят в первую половину получающегося при этом массива, а элементы, занимающие нечетные позиции, переходят во вторую половину. Мы применяем эти функции только к подмассивам, содержащим четное число элементов.

template <class Itein> void shuffle(Item a[], int 1, int r) { int i, j, m = (l+r)/2; static Item aux[maxN]; for (i = 1, j = 0; i <= r; i+=2,

{ aux[i] = a[l+j]; aux[i+1] = a[m+l+j]; } for (i = 1; i <= r; i++) a[i] = aux[i];

template <class Item>

void unshuffle (Item a[], int 1, int r) { int i, j, m = (l+r)/2; static Item aux{maxN] ; for (i = 1, j = 0; i <= r; i+=2,

{ aux[l+j] = a[i]; aux[m+l+j] = a[i+l]; } for (i = 1; i <= r; i++) a[i] = aux[i];

Сортировка Бэтчера представляет собой в точности нисходящую сортировку слиянием, описанную в разделе 8.3; различие состоит лищь в том, что вместо одной из адаптивных реализаций слияний из главы 8 она использует нечетно-четное слияние Бэтчера, представляющее собой неадаптивное нисходящее рекурсивное слияние. Профамма 8.3 сама по себе вообще не выполняет доступа к данным, так что из факта использования нами неадаптивного слияния следует, что и сама сортировка неадаптивная.

На протяжении этого раздела и раздела 11.2 мы неявно предполагаем, что число сортируемых элементов является степенью 2. Следовательно, мы всегда можем употребить значение N/2 , не опасаясь того, что - нечетное. Это предположение условно - рассматриваемые нами программы и примеры рассчитаны на любые размеры файлов, тем не менее, оно существенно упрощает нащи рассуждения. К этой проблеме мы вернемся в конце раздела 11.2.

Слияние Бэтчера само по себе является рекурсивным методом разделяй и властвуй . Чтобы выполнить слияние 1-с-1, мы употребляем только одну операцию сравнения-обмена. Во всех прочих случаях, для выполнения слияния N-c-N мы осуществляем обратное тасование, чтобы свести эту задачу к двум задачам слияния N/2-c-N/2, после чего решаем их в рекурсивном режиме, в результате чего получаем два отсортированных файла. Тасуя эти файлы, мы получаем почти отсортированный файл; все, что теперь нам нужно - это один проход для выполнения N/2 - 1 независимых друг

от друга операций сравнения-обмена между элементами 2/ и 2/ + 1, где / пробегает значения от 1 до N/2 - \. Соответствующий пример показан на рис. 11.2. Это описание позволяет без труда написать программу 11.2.

Почему этот метод сортирует все возможные перестановки входных данных? Ответ на этот вопрос далеко не очевиден; классическое доказательство этого факта - это на самом деле косвенное доказательство, которое построено на общих характеристиках неадаптивных программ сортировки.

Программа 11.2. Нечетно-четное слияние Бэтчера (рекурсивная версия)

Эта рекурсивная программа реализует абстрактное обменное слияние, используя для этой цели операции shuffle и unshuffle из программы 11.1, хотя это и не обязательно - программа 11.3 представляет собой нерекурсивную версию данной программы, в которой тасование не используется. Основной интерес для нас представляет тот факт, что рассматриваемая реализация является компактным описанием алгоритма Бэтчера, когда размер файла является степенью 2.

template <class Item>

void merge(Item a[], int 1, int m, int r)

if (r = 1+1) compexch(a[1] , a[r]); if (r < 1+2) return; unshuffle(a, 1, r) ; merge(a, 1, (l+m)/2, m); merge(a, m+1, (m+l+r)/2, r); shuffle(a, 1, r) ; for (int i = 1+1; i < r; i+=2) compexch(a[i], a[i+1]) ;

Лемма 11.1. (Принцип нулей и единиц) Если неадаптивная программа выдает отсортированный выход в случае, когда входы состоят только из О и 1, то она делает то же, когда входами являются произвольные ключи.

См. упражнение 11.7.

Лемма 11.2. Нечетно-четное слияние Бэтчера (программа \\.2) это правильный метод слияния

Опираясь на принцип нулей и единиц, мы проверяем только, правильно ли работает метод слияния, когда входами являются нули и единицы.

лее g n r

l м р x y т е l р y

g r g е е g

N Т L Y

а е а g е а а е е g

е l g

е g l

l i n м р о

i l м n о р

РИСУНОК 11.2. ПРИМЕР ВЫПОЛНЕНИЯ НИСХОДЯЩЕГО НЕЧЕТНО-ЧЕТНОГО СЛИЯНИЯ БЭТЧЕРА

Чтобы слить AGINORSTc AEEL МРХ Y, мы начнем с того, что выполним операцию обратного тасования, которая приводит к возникновению двух независимых друг от друга задач слияния наполовину меньших массивов (показаны во второй строке): нам надо слить А IО S с АЕ MX (в первой части массива) и GNR TcELPY (во второй части массива). После того, как эти подзадачи будут решены в рекурсивном режиме, мы тасуем массивы, полученные в результате решения этих подзадач (полученные в предпоследней строке) и завершаем эту сортировку выполнением операций сравнения-обмена Е с А, GcE,LcI,NcM,Pc 0,Rc SuTcX.

Предположим, что в первом подфайле содержатся / нулей и j нулей во втором подфайле. Доказательство этой леммы требует рассмотрения четырех случаев в зависимости от того, являются ли / и j четными или нечетными числами. Если обе переменные имеют четные значения, то две подзадачи слияния выполняется над двумя файлами, при этом один файл содержит 2 нулей, а другой файл - j / 2 нулей, так что в обоих случаях получившийся при слиянии файл содержит {/+j) /2 нулей. Выполнив тасование, получим сортированный файл типа 0-1. Файл типа 0-1 подвергается тасованию и в тех случаях, когда / - четное, а j - нечетное число, а также когда / - нечетное, а j - четное число. Но если оба i и j - нечетные числа, то мы завершаем эту процедуру тем, что тасуем файл, содержащий (i + j) / 2 + 1 нулей с файлом, содержащим (/ + у) / 2 - 1 нулей, следовательно, полученный после тасования файл содержит / +у- 1 нулей, единицу, ноль и N - i-j- 1 единиц (см. рис. 11.3), и один из компараторов на завершающей стадии заканчивает сортировку.

00111111000011 О111ОО1101110О 0O011111Q001 000000111111 000000111111

ОО111111О0О1 011100110111 000111110011 000001111111 000001111111

011111110000 011100111111 ООО11111С011 000001111111 000001111111

000111110001 001100110111 000011110011 00000101 111 1 000000111111

рисунок 11.3. четыре случая слияния типа 0-1.

Каждому из четырех примеров отводится по 5 строк: задача слияния типа 0-1, результат выполнения операции обратного тасования, поторый порождает две подзадачи слияния; результат рекурсивного завершения слияний; результат тасования и результат завершающих нечетно-четных сравнений. На последней стадии обмен выполняется только, когда число нулей в обоих входных файлах нечетно.

На самом деле нет необходимости тасовать данные. И действительно, мы можем переделать программы 11.2 и 8.3 таким образом, чтобы на выходе они имели неветвящуюся сортирующую программу для любого N, скорректировав функции compexch и shuffle с тем, чтобы они поддерживали индексы и осуществляли косвенные обращения к данным (см. упражнение 11.12). Либо мы можем заставить эту программу генерировать последовательность команд

сравнения-обмена для последующего применения к исходному входному файлу (см. упражнение 11.13). Мы можем использовать эти приемы для любого неадаптивного метода сортировки, который выполняет переупорядочивание данных при помощи операций обмена, тасования или им подобных. Что касается слияния Бэтчера, то структура этого алгоритма настолько проста, что мы сразу можем приступить к разработке восходящей программной реализации, в чем убедимся уже в разделе 11.2.

Упражнения

> 11.1. Покажите результат тасования и обратного тасования клучей Е А S Y Q U Е S Т IO N.

11.2. Обобщить программу 11.1 на случай, когда нужно выполнить Л-путевое тасование и обратное тасование.

11.3. Реализовать операции тасования и обратного тасования без использования вспомогательного массива.