AOP_Tom3 (1021738), страница 36
Текст из файла (страница 36)
Если вы дошли до этого места, то н так уже слишком много знаете. С. Новая суперметодика сорпгировки. Это существенно усовершенствованные известные методы. (Если вы нашли такую методику, яожалуйстаг немедленно сообщите об этом автору.) Если бы данная задача была сформулирована, скажем, для 1 000 элементов, а не для 5, то вы могли бы открыть и более тонкие методы, о которых речь пойдет ниже. В любом случае, приступая к новой задаче, разумно найти какую-нибудь очевидную процедуру, а затем попытаться улучшить ее.
Развитие вариантов А, В и С приводит к появлению важньгх классов методов сортировки, которые представляют собой усовершенствованные сформулированные выше простые идеи. Было изобретено множество различных алгоритмов сортировки, и н этой книге рассматривается около 25 из иих. Такое пугающее количество методов на самом деле — - лишь малая толика всех алгоритмов, придуманных на сегодняшний день; многие уже устаревшие методы мы вовсе не будем рассматривать или упомянеи лишь вскользь. Почему же существует так много методов сортировкиу Применительно к программированию зто частный случай вопроса "Почему существует так много методов х7", где х пробегает множество всех задач.
Ответ если и неочевиден, то вполне понятен — каждый метод имеет свои преимущества и недостатки, поэтому он оказывается эффективнее других при некоторых конфигурациях данных и аппаратуры. К сожалению, неизвестен наилучший способ сортировки (если он вообще существует); имеется много наилучших методов, но только в случаях, когда известно, что сортируется, на каком компьютере и с какой целью.
Говоря словами Редьярда Киплинга, "существует 9 и еще 60 способов сложить песню племени, и каждый из них в отдельности хорош". Полезно изучить характеристики каждого метода сортировки, чтобы для конкретного случая можно было сделать разумный выбор. К счастью, эта задача не столь уж громоздка, поскольку алгоритмы взаимосвязаны подчас самым причудливым способом. В начале этой главы мы ввели основную терминологию и обозначения, которые и будем использовать при изучении сортировки. Записи Вы Йг ., Л~ч должны быть рассортированы в порядке неубывания своих ключей Кы Кт,..., Кв, т. е.. .по существу, нужно найти перестановку р(1) р(2)... р(Х), такую, что (2) к„„<к„, «" к„,,, В этом разделе рассматривается внутргннлл сортировка, когда число записей, подлежащих сортировке, достаточно мало, так что весь процесс можно провести в оперативной памяти компьютера, обладающей высоким быстродействием.
В одних случаях может понадобиться физически переставлять записи в памяти так, чтобы их ключи были упорядочены; в других можно обойтись вспомогательной таблицей некоторого вида, определяющей перестановку. Если записи и/или ключи занимают несколько слов памяти, то часто лучше составить новую таблицу адресных ссылок, которые указывают на записи, н работать с этими ссылками, не перемещая громоздкие записи. Такой метод называется сортировкой таблицы адресов (рис. 6). Если ключи короткие, а сопутствующая информация в записях велика.
то для повышения скорости ключи можно вынести в таблипу адресных ссылок. Этот процесс называется сортировкой ключей. В других схемах сортировки используется вспомогательное поле связи, которое включается и каждую запись. Связи обрабатываются таким образом, что в результате все они оказываются объединенными в линейный список, в котором каждая связь указывает на следующую по порядку запись. Этот способ называется сортировкой списка (рис.
7). После сортировки таблицы адресов или списка можно по желанию расположить записи в порндке неубывания. Сделать это можно несколькими способами, требующими дополнительной памяти для хранения всего одной записи (см. упр. 10 и 12): или же можно просто переместить записи в новую область памяти, если она способна вместить все эти записи. Последний способ обычно вдвое быстрее первого, по требует почти в два раза болыне памяти.
Во многих приложениях вовсе не й~ Нг нг Ключ Записи Сопутствующая информация сортировки Дополнительная табл е сортировки Рнс. б. Сортировка таблипы адресных ссылок. лг лз люч Сопутствующая информация опе связи (после сортироякп] Голова списка Рнс. Т.
Сортировка списка. обнэательно перемещать записи, так как поля связи, как правило, вполне приемлемы для всех последующих операций обработки. Все методы сортировки, которые мы исследуем пдоскональво", будут проиллюстрированы четырьмя способамн: посредством а) словесного описания алгоритма, Ь) блок-схемы, с) программы для машины И1Х, е1) примера применения этого метода сортировки к некоторому множеству из 16 чисел. Программы для компьютера И1Х будут, как правило, написаны в предположении, что ключ -- числовой и что он помещается в одном слове; иногда мы даже будем ограничивать значения ключей так, чтобы они занимали лишь часть слова.
Отношением порядка < будет обычное арифметическое отношение порядка, а записи будут состоять из одного ключа, без сопутствующей информации. Эти предположения позволяют сделать программы более короткими и простыми для понимания, н не составляет труда распространить их на общий случай (например, применяя сортировку таблиц адресов). Вместе с программами для И1Х приводится анализ времени выполнения соответствующего алгоритма сортировки. Сортировка посредством подсчета. Чтобы проиллюстрировать, как мы будем анализировать методы внутренней сортировки, рассмотрим идею "подсчета", упомннутую в начале данного раздела.
Этот простой метод основан на том, что у-й ключ в окончательно упорядоченной последовательности превышает ровно у — 1 остальных ключей. Иначе говоря, если известно, что некоторый ключ превышает ровно 27 дру- гих и если никакие два ключа не равны, то после сортировки соответствующая запись должна занять 28-е место.
Таким образом, идея состоит в том, чтобы сравнить попарно все ключи и подсчитать, сколько из них меньше каждого отдельного ключа. Очевидный способ выполнения поставленной задачи таков: [(сравнить К с К,) при 1< 1 < Х) прн 1 <1 < Х; но нетрудно заметить, что более половины этих операций излишни, поскольку не нужно сравнивать ключ сам с собой и после сравнения К, с Кэ уже не надо сравнивать Кэ с К,. Поэтому достаточно ((сравнить К с К;) при 1 < 1 <1) при 1 < 1 < Х. Итак, получаем следующий алгоритм. Алгоритм С (Подсчет сравнений). Этот алгоритм (рис.
8) сортирует записи Лы..., Лм по ключам Кы..., Ки, используя вспомогательную таблицу СООМТ [Ц, ..., СООМТ[Ат) для подсчета числа ключей, меньших данного. После завершения алгоритма величина СООМТ [Я + 1 определяет окончательное положение записи Л .. С1. [Сбросить счетчики СООМТ.] Установить в счетчиках СООМТВЦ вЂ” СООМТ [%1 нули. С2.
[Цикл по 1.] Выполнить шаг СЗ при ю' = Х, Х вЂ” 1, ..., 2; затем завершить выполнение процедуры. СЗ. [Цикл по Д Выполнить шаг С4 при 1' = 1 — 1, ю'-2, ..., 1. С4. [Сравнить К;: К .] Если К, < К., то увеличить СООМТ[Я на 1; в противном случае увеличить СООМТ[Ц на 1. Обратите внимание на то, что в данном алгоритме записи не перемещаются. Он аналогичен алгоритму сортировки таблицы адресов, поскольку таблица СООМТ определяет конечное положение записей, но эти методы несколько различаются, потому что СООМТ указывает, куда нужно переслать запись Лз, а не запись, которую надо переслать на место Л.. (Таким образом, таблица СООМТ определяет перестановку, обратную перестановке р(1)...р(Ж); см.
раздел 5.1.1.) В табл. 1 проиллюстрирован типичный ход событий при подсчете сравнений. Использован пример с 16 случайными числами, которые были выбраны автором еще 19 марта 1963 года.Те же самые 16 чисел будут использованы в примерах, иллюстрирующих и другие методы, анализ которых еше впереди. В рассуждении, предшествующем этому алгоритму, мы не учитывали, что ключи могут быть равными. Это, вообще говоря, серьезное упущение, которое может повлечь за собой самые опасные последствия, потому что если бы равным ключам соответствовали равные счетчики, то заключительное перемещение записей было бы довольно сложным. К счастью, как показано в упр.
2, алгоритм С дает верный результат независимо от числа равных ключей. Программа С (Подсчет сравнений). Ниже приведена программа для М11, реализующая алгоритм С в предположении, что Лз хранятся по адресу 1МРОТ+ 1, а СООМТ[Я вЂ” по адресу СООМТ+ у, где 1 < у < Х; состояние регистров следующее: гП = 1, г12 = 1, гА э— з К,: — Лп гХ = СООМТ[П. 01 ЯТАМТ ЕМТ1 М 1 С1. Очистка СОУМТ. 00 ЯТЕ СООМТ,1 Х СООМТОВ <- О. Таблица 1 СОРТИРОВКА ПОСРЕДСТВОМ ПОДСЧЕТА (АЛГОРИТМ С) 612 677 765 703 О 0 0 0 0 0 1 12 0 0 13 12 0 11 13 12 9 11 13 12 9 11 13 12 9 11 13 12 42 6 154 509 0 О О 0 0 0 0 0 О О 0 0 0 О 0 0 0 7 1 2 7 061 908 170 0 0 0 О 1 О 0 2 0 0 3 0 0 4 0 0 5 0 О 6 1 897 275 653 0 О 0 1 О 0 2 0 О 3 0 0 4 О 1 5 0 2 6 1 3 503 087 512 0 0 0 0 0 О 0 О 0 0 0 0 О 0 О О 0 1 1 0 2 КЛЮЧИ: СОПИТ (нач.) СО!Л1Т (г = 1Ч): Со!Л4Т (г = Лг — 1): СОЛТ (г = Лг-2): СОМЛ1Т (г = Лг-3): СООИТ (г = 1Ч вЂ” 4): СОПМТ (г = Л' — 5); Сопит (! = 2): 6 1 8 0 15 3 14 4 10 5 2 7 9 11 13 12 Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
