Специальные методы сортировки a

Рис. 11.1. Идеальное тасование и идеальное обратное тасование
Для выполнения идеального тасования (слева) берется первый элемент файла, затем первый элемент из второй половины файла, затем второй элемент файла, второй элемент из второй половины файла и т.д. Если перенумеровать элементы сверху вниз, начиная с 0, то элементы из первой половины попадут в четные позиции, а элементы из второй половины - в нечетные позиции. Для выполнения идеального обратного тасования (справа) выполняется обратная процедура: элементы из четных позиций попадают в первую половину файла, а элементы из нечетных позиций - во вторую половину.
Лишь немногие из алгоритмов, рассмотренных в главах 6-10, являются неадаптивными: все они используют операцию <, либо как-то по-другому анализируют ключи, после чего выполняют действия в зависимости от значений ключей. Одним из исключений является пузырьковая сортировка (см. "Элементарные методы сортировки" ), использующая только операции сравнения-обмена. Еще одним примером неадаптивного метода сортировки служит версия Пратта сортировки Шелла (см. "Элементарные методы сортировки" ).
В программе 11.1 приведена реализация других абстрактных операций, которыми мы будем пользоваться в дальнейшем - операции идеального тасования и операции идеального обратного тасования, а на рис. 11.1 приведены примеры каждой из них. Идеальное тасование переупорядочивает массив так, как тасует колоду карт опытный картежник: колода делится точно пополам, затем карты по одной берутся из каждой половины колоды. Первая карта всегда берется из верхней половины колоды. Если число карт в колоде четное, в обеих половинах содержится одинаковое их число, если число карт нечетное, то лишняя карта будет последней в верхней половине колоды.
Программа 11.1. Идеальное тасование и идеальное обратное тасование
Функция shuffle переупорядочивает подмассив a[l], ..., a[r] с помощью деления этого подмассива пополам и чередования элементов из каждой половины массива: элементы из первой половины заносятся в четные позиции результирующего массива, а элементы из второй половины - в нечетные позиции. Функция unshuffle выполняет обратное действие: элементы из четных позиций заносятся в первую половину результирующего массива, а элементы из нечетных позиций - во вторую половину. Мы будем применять эти функции только к подмассивам, содержащим четное число элементов.
template
void shuffle(Item a[], int l, int r)
{ int i, j, m = (l+r)/2;
static Item aux[maxN];
for (i = l, j = 0; i <= r; i += 2, j++)
{ aux[i] = a[l+j]; aux[i+1] = a[m+1+j]; }
for (i = l; i <= r; i++) a[i] = aux[i];
}
template
void unshuffle(Item a[], int l, int r)
{ int i, j, m = (l+r)/2;
static Item aux[maxN];
for (i = l, j = 0; i <= r; i += 2, j++)
{ aux[l+j] = a[i]; aux[m+1+j] = a[i+1]; }
for (i = l; i <= r; i++) a[i] = aux[i];
}
Идеальное обратное тасование выполняет обратную процедуру: карты попеременно откладываются в верхнюю и нижнюю половину колоды.
Сортировка Бэтчера почти точно совпадает с нисходящей сортировкой слиянием из "Слияние и сортировка слиянием" ; различие состоит лишь в том, что вместо одной из адаптивных реализаций слияния из "Слияние и сортировка слиянием" она использует нечетно-четное слияние Бэтчера - неадаптивное нисходящее рекурсивное слияние. Программа 8.3 сама по себе вообще не обращается к данным, а поскольку используется неадаптивное слияние, то и сама сортировка будет неадаптивной.
На протяжении этого раздела и раздела 11.2 неявно предполагается, что количество сортируемых элементов является степенью 2. Поэтому всегда можно использовать выражение " N/2 " , не опасаясь того, что N - нечетное. Конечно, это предположение практически нереально: рассматриваемые нами программы и примеры работают с файлами любых размеров, однако оно существенно упрощает рассуждения. Мы еще вернемся к этому вопросу в конце раздела 11.2.
Слияние Бэтчера само по себе является рекурсивным методом " разделяй и властвуй " . Для выполнения слияния 1-и-1 нужна только одна операция сравнения-обмена. Во всех прочих случаях, для выполнения слияния N-и-N эта задача сводится обратным тасованием к двум задачам слияния N/2-и-N/2, после рекурсивного решения которых получаются два отсортированных файла. Тасованием этих файлов получается почти отсортированный файл; все, что теперь нужно - это один проход для выполнения N/2 - 1 независимых операций сравнения-обмена между элементами 2i и 2i + 1, для i от 1 до N/2 - 1. Соответствующий пример показан на рис. 11.2. Из этого описания непосредственно следует программа 11.2.
Программа 11.2. Нечетно-четное слияние Бэтчера (рекурсивная версия)
Данная рекурсивная программа реализует абстрактное обменное слияние, используя для этой цели операции shuffle и unshuffle из программы 11.1, хотя это и не обязательно - программа 11.3 представляет собой нерекурсивную версию данной программы, в которой тасование не используется. Самое интересное здесь то, что если размер файла является степенью 2, то эта реализация является компактным описанием алгоритма Бэтчера.
template
void merge(Item a[], int l, int m, int r)
{ if (r == l+1) compexch(a[l], a[r]);
if (r < l+2) return;
unshuffle(a, l, r);
merge(a, l, (l+m)/2, m);
merge(a, m+1, (m+1+r)/2, r);
shuffle(a, l, r);
for (int i = l+1; i < r; i += 2)
compexch(a[i], a[i+1]);
}