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

Мы достаточно подробно рассматривали эти моменты в главе 5, однако привлекательность преждевременной оптимизации настоль сильна, что каждый раз, когда изучается возможность применения того или иного метода усовершенствования реализации rta таком уровне детализации, целесообразно подумать об улучшении самих методов. Что касается оптимизации сортировки слиянием, то здесь можно чувствовать себя вполне спокойно, ибо программы 8.1-8.4 обладают всеми наиболее важными характеристиками производительности, которые исследовались выше: время их выполнения пропорционально NlogN, они нечувствительны к организации входных данных (см. рис. 8.8), они используют дополнительное пространство памяти, они могут бьггь реализованы с сохранением свойства устойчивости. Сохранение этих свойств в процессе снижения времени выполнения в общем случае не является особо трудной задачей.

Упражнения

8.31. Реализовать восходящую сортировку слиянием без копирования массивов.

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

8.7. Реализация сортировки слиянием, ориентированной на связные списки

Для практической реализации в любом случае требуется дополнительное пространство памяти, так почему бы не рассмотреть возможность реализации сортировки слиянием, ориентированной на связные списки? Другими словами, чем тратить дополнительное пространство памяти на вспомогательный массив, не лучше ли использовать его для хранения связей? Иначе можно столкнуться с проблемой предварительной сортировки связного списка (см. раздел 6.9). Как оказалось, сортировка слиянием может быть успешно использована для сортировки связных списков. Полная реализация функции сортировки связных списков представлена в программе 8.6. Обратите внимание на то обстоятельство, что в данном случае программа фактического слияния столь же проста, как и программа процедуры слияния, ориентированная на массивы (программа 8.2).

Имея в своем распоряжении такую функцию слияния, легко получить рекурсивную нисходящую сортировку слиянием списков. Программа 8.7 является прямой рекурсивной реализацией функции, которая принимает в качестве входного параметра указатель на неупорядоченный список и возвращает указатель на список, содержащий те же элементы в отсортированном порядке. Эта программа выполняет свою работу, переупорядочивая узлы списка - память не резервируется ни для временных узлов, ни для списков. Для нахождения середины списка программа 8.7 использует следующий прием: разные реализации могут делать это либо передавая длину списка как параметр в рекурсивную программу, либо сохраняя длину в самом списке. Такая программа в рекурсивной формулировке проста для понимания, даже если реализует достаточно сложный алгоритм.

Восходящий подход объединяй и властвуй можно также применить и по отнощению к сортировке слиянием связных списков, хотя необходимость отслеживать связи со всеми подробностями делают его более сложным, чем он кажется на первый взгляд. Как было установлено в разделе 8.3 при рассмотрении нисходящих методов, ориентированных на работу с массивами, при разработке алгоритма восходящей сортировки списков слиянием не существует особых причин придерживаться точно того же набора операций слияния, которые выполняют рекурсивная версия или версия, использующая массивы.

Программа 8.6. Слияние связных списков

Данная программа сливает список, на который указывает а, со списком, на который указывает Ь, с помощью вспомогательного указателя с. Операция сравнения ключей в функции merge включает равенство, так что слияние будет устойчивым, если по условию список b следует за списком а. Для простоты принимаем, что все списки завершаются символом 0. Другие соглашения, касающиеся завершающих элементов в списках, также работают (см. табл. 3.1). Что еще важнее, мы не используем заголовочные узлы списка во избежание их распространения.

link merge (link а, link Ь) { node dummy (0); link head = Sdummy, с = head; while ((a != 0) && (b != 0)) if (a->item < b->item)

{ c->next = a; с = a; a = a->next; } else

{ c->next = b; с = b; b = b->next; } c->next = (a == 0) ? b : a; return head->next;

Одна из забавных версий восходящей сортировки связных списков слиянием, которую нетрудно сформулировать, напращивается сама собой: поместить элементы списка в циклический список, после чего перемещаться по списку, сливая пары упорядоченных подфайлов до тех пор, пока дело не будет сделано. Этот метод концептуально прост, однако (как это имеет место в случае низкоуровневых программ, работающих со связными списками) для их реализации требуется проявить недюжинную изобретательность (см. упражнение 8.36). Другая версия восходящей сортировки связных списков слиянием, в основу которой положена та же идея, представлена в программе 8.8: содержать все сортируемые списки в рамках АТД очереди. Этот метод

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

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

Программа 8.7. Сортировка связных списков слиянием сверху вниз

Эта программа выполняет сортировку, разбивая список, на который указывает с, на две части, на которые указывают, соответственно, а и Ь, подвергая сортировке обе эти части в рекурсивном режиме, с последующим использованием функции merge (программа 8.6) для получения окончательного результата. В конце входного файла должен стоять символ О (и следовательно, список b также должен завершаться нулем), а явно определенная команда c->next = О помещает О в конец списка а.

link mergesort(link с) {

if (с == О II c->next = 0) return с;

link а = с, b = c->next;

while ((b != 0) && (b->next != 0))

{ с = c->next; b = b->next->next; } b = c->next; c->next = 0; return merge(mergesort(a), mergesort(b));

Программа 8.8. Восходящая сортировка связных списков слиянием

Эта программа использует АТД очереди (программа 4.18) для реализации восходящей сортировки слиянием. Элементы очереди представляют собой упорядоченные связные списки. После инициализации очереди списком длиной 1, программа просто удаляет из очереди два списка, сливает их, а полученный результат возвращает в эту же очередь и продолжает процесс до тех пор, пока в очереди не останется только один список. Это соответствует последовательности проходов через все элементы, при этом на каждом проходе длина упорядоченных списков удваивается, как и в случае восходящей сортировки слиянием.

link mergesort(link t) { QUEUE<link> Q(max); if (t == 0 II t->next == 0) return t; for (link u = 0; t 0; t = u)

{ u = t->next; t->next = 0; Q.put(t); ) t = Q.getO; while (! Q. empty 0)

{ Q.put(t); t = merge (Q.getO , Q.getO); ) return t;