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

i++) datasorted[i] =

for (i=0; i data[a[i]];

< N;

тривиален, однако требует дополнительного пространства памяти, достаточного для размещения еще одной копии массива. Что делать в том случае, когда для второй копии файла в памяти не хватает места? Ведь нельзя же просто записать data[i] = data[a[i]], ибо в этом случае предыдущее значение data[i] окажется затертым, и скорее всего, преждевременно.

На рис. 6.15 показан способ решения этой проблемы, все еще обходясь одним проходом по файлу. Чтобы переместить первый элемент на положенное ему место, мы переносим элемент, который находится на его месте, на положенное ему место и т.д. Продолжая подобные рассуждения, мы в конце концов находим элемент, который требуется передвинуть на первую позицию; на этом этапе в окончательные позиции оказывается сдвинутым некоторый цикл элементов. Далее, мы переходим ко второму элементу и выполняем те же операции для его цикла и так далее (любые элементы, с которыми мы сталкиваемся и которые находятся в своих окончательных позициях (a[i] = i), попадают в цикл длиной 1 и не перемещаются).

В частности, для каждого значения i сохраняется значение data[i] и инициализируется индексная переменная к значением i. Далее мы обращаем свое внимание к образовавшемуся пустому месту в позиции i и ищем элемент, который должен заполнить это место. Таким элементом является data[a[k]] - другими словами, операция присваивания data[k] = data[a[k]] перемещает это пустое место в а[к]. Теперь пус-

aaeeg i lmnoprstx

РИСУНОК 6.15. ОБМЕННАЯ СОРТИРОВКА

Чтобы выполнить обменное упорядочение массива (упорядочение на месте), мы перемещаемся по нему слева направо, в циклах передвигая элементы, которые требуется переместить. В рассматриваемом примере имеются четыре цикла: первый и последний суть вырожденные одноэлементные циклы. Второй цикл начинается с позиции L Элемент S переходит во временную переменную, оставляя в позиции 1 пустое место. Перемещение второго А приводит к тому, что в позиции 10 остается пустое место. Это пустое место заполняется элементом Р, который, в свою очередь, оставляет пустое место в позиции 12. Это пустое место должно быть заполнено элементом в позиции 1, следовательно, запомненный элемент S переходит в это пустое место, тем самым завершая цикл 11012, который устанавливает эти элементы в окончательные позиции. Аналогично выполняется цикл 2 8 613 4 711314 9, который и завершает сортировку.

тое место возникает в позиции data[a[k]], таким образом, к устанавливается в а[к]. Повторяя эти действия, мы в конце концов оказываемся в ситуации, когда пустое место должно быть заполнено значением data[i], которое было предварительно сохранено. Когда мы помещаем элемент в какую-либо позицию, мы вносим соответствующие изменения в массив а. Для любого элемента, занявшего свою позицию, а[к] равен i, и только что написанный процесс сводится к отсутствию операции (no-op). Перемещаясь по массиву и начиная новый цикл всякий раз, когда встречается элемент, который еще ни разу не перемещался, мы перемещаем каждый элемент самое большее один раз. Программа 6.14 представляет реализацию рассмотренного процесса.

Программа 6.14. Обменная сортировка

Массив data[0],...,data[N-1] должен быть упорядочен на месте в соответствии с массивом индексов a[0],...,a[N-1]. Любой элемент, для которого a[i] == i, занимает свое окончательное место и его больше не следует трогать. В противном случае следует сохранить data[i] в v и работать в цикле а[1], a[a[i]], a[a[a[i]]] и т.д. до тех пор, пока индекс 1 не встретится опять. Мы повторяем этот процесс для следующего элемента, который не на месте, и продолжаем в том же духе, пока не приведем в порядок весь файл, причем каждая запись будет перемещаться только один раз.

template <class Item>

oid insitu(Item data[]. Index a[] , int N) { for (int i = 0; i < N; i++) { Item V = data[i]; int j, k;

for (k = i; a[k] != i; к = a[j], a[j] = j)

{ j = k; data[k] = data[a[k]]; } data[k] = v; a[k] = k;

Этот процесс называется перестановкой по месту (in situ) или обменное упорядочение файла. Отметим еще раз: несмотря на то что сам по себе алгоритм весьма интересен, тем не менее, во многих приложениях в нем нет необходимости, ибо вполне достаточно непрямого доступа к элементам. Кроме того, если записи несопоставимо велики по отношению к их номерам, наиболее эффективным может оказаться вариант их упорядочения при помощи обыкновенной сортировки выбором (см. лемму 6.5).

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

Упражнения

6.57. Представить реализацию типа данных для элементов, когда элементами являются записи, а не указатели на записи. Такая организация данных может оказаться предпочтительной для применения программ 6.12 и 6.13 к небольшим записям. (Не забывайте, что язык С++ поддерживает операцию присваивания структур.)

о 6.58. Показать, как можно использовать функцию qsort для решения проблем сортировки, на которые ориентированы программы 6.12 и 6.13.

> 6.59. Построить массив индексов, который получается при индексной сортировке ключей EASYQUESTION.

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

6.61. Опишите перестановку размера N (набор значений для массива а), в которой условие a[i] != i в процессе работы программы 6.14 выполняется максимальное число раз.

6.62. Доказать, что в процессе перемещения ключей и появления в программе 6.14 пустых мест мы обязательно вернемся к ключу, с которого начинали.

6.63. Реализовать программу, аналогичную программе 6.14, с сортировкой по указателям в предположении, что указатели указывают на массив из записей типа Item.

6.9. Сортировка связных списков

Как стало известно из главыЗ, массивы и связные списки представляют собой два базовых способа структурирования данных, поэтому рассмотрим реализацию сортировки вставками связных списков как пример обработки списков, о которой шла речь в разделе 3.4 (программа 3.11). Все программные реализации сортировок, рассмотренные к этому моменту, предполагают, что сортируемые данные представлены в виде массивов, в связи с чем они не могут быть использованы непосредственно, если мы работаем в рамках системы, которая использует связные списки для организации данных. В некоторых случаях могут оказаться полезными специальные алгоритмы, но только тогда, когда они по существу выполняют последовательную обработку данных, которую можно эффективно поддерживать для связных списков.

Программа 6.15. Определение интерфейса для типа связного списка

Данный интерфейс для связных списков может быть сопоставлен с интерфейсом для массивов, представленным в программе 6.7. Функция randomlist строит список случайно распределенных элементов с одновременным выделением для них памяти. Функция showlist выполняет печать ключей из этого списка. Программы сортировки используют перегруженную операцию operator< для сравнения и манипулирования указателями с целью упорядочения элементов. Представление данных в узлах реализуется обычным способом (см. главу 3) и включает конструктор узлов, который заполняет каждый новый узел заданными значениями и наделяет фиктивной связью.

struct node { Item item; node* next;