Искусство программирования на Си (984073), страница 41
Текст из файла (страница 41)
Если количество элементов действительно очень велико (слишком велико для хранения их в памяти),может быть, придется ограничивать количество элементов, которые могут быль отсортированы одновременно. Поскольку поиск и чтение на диске занимает намного больше времени, чем работа с памятью, выгоднее хранить в памяти максимально возможное количество элементов. ственно с ключами.
На первом проходе подсчитываются вхождения каждого ключа в массив смещений, а затем подсчитывается промежуточная сумма, н казкдая точка смещений оказывается точкой вставки нового элемента. При втором проходе элемент переносится в его окончательное положение в соответствии с точкой смешения для этого ключа. В сортировке методом подсчета предполагается, что ключи являются целыми числами от 0 до )с, где к — константа.
Часто выбирается й=()СНАЯ МАХ В этом случае за один прием'будет обрабатываться один символ данных. Такой выбор совершенно произволен. Вполне можно принять )гтЮБНКТ МАХ, но тогда потребуется гораздо больше дополнительной памяти и много времени может уйтить на просмотр пустых ведер. Эффективность сортировки методом подсчета равна 0(п+)г), или О(п), если (с имеет порядок О(п). Это позволяет получить очень высокую скорость сортировки для элементов нз ограниченного диапазона.
Обратите внимание, что данный метод символа имеется контейнер. Содержимое этого контейнера вычисляется таким же образом, как и в сортировке мсзозом подсчета. На каждом последующем проходе на основании текущего символа определяется, в какон контейнер переместить запись. Этот процесс повторясзся для каждого символа в ключе от менее значащего к более значащему. Данный метод работает только поточу, что метод сортировки подсчетом устойчив. Но мы не используем такой метод.
Можно было бы испольювать метод сортировки слиянием, который тоже явэясн я устойчивым, но на практике это никогда не лелается Поразрядная сортировка выполняется в случае, когда ключи маленькие или когда количество элементов просто огромно. Для огромного количества элементов сортировка слиянием будет неэффективна, или, по крайнсн мере, не так эффективна,как сортировка подсчетом.
Ускоренная восходящая поразрядная сортировка поразрядной сортировки является то, что она не требует устойчивых алгоритмов сортировки, как восходящая поразрядная сортировка. Это означает, что можно использовать методы быстрой соятировки, сортировки Шелла или любой другой алгоритм сортировки. В последнее время были разработаны новые усоверпсенствованные алгоритмы поразрядной сортировки, например, адаптивная поразрядная сортировка н поразрядная сортировка вперед, которые в настоящее время проходят тестирование. Неплохо в этой области поработал Стефан Нильсон (бге(ап МЬьоп). Поразрядная сортировка произвольных типов данных Наверное, в любой книге по сортировке вы прочтете, что поразрядную сортировку нельзя использовать произвольным образом подобно сортировке сравнением.
Но это не так. Поразрядная сортировка, которая основана на сортировке подсчетом, является совершенно отдель- Глава 13 Ореонизоиие данных Метод» бисерно еортироени Часть И байтов. /т теперь рассмотрим некоторые короткие клю- но 33554432, скорости поразрядной сортировки и ме- ) чи.
Представьте себе, что длина ключа составляет 24 нее "оптиматьной" сортировки порядка О(п"1ок(п)) сравсимвола. Поскольку время поразрядной сортировки нлютсл при сортировке 33554432 элементов. 2(ругими ) пропорционально длине ключа, алгоритму восхоллшей словами, линейные алгоритмы сортировки неэффективпоразрядной сортировки потребуется и'25 проходов. Но ны даже при средней длине ключа. Можно, конечно, если использовать метод сортировки порядка и'1оп(п), выбрать гибридную стратегию или использовать поразто )оп(п) здесь будет больше, чем 25. Поскольку 2" рав- рядную сортировку только для ключей небольшой дли- Л инг 13.6. Восходящая пор зрядная сор ировка. ны (листинги 13.5 и 13.6). /» Листинг 13.5.
Нисходящая поразрядная сортировка. восходяяая доразрядвая сортвровка. Основана ва оппсаввв, приведенном в Л1дог(евна 1п с" ВоЬегг Ведден(св, 10ВИе0-201-31452-5. /* Здесь бнл введен оператор СВОИК, авалогвчвнй оператору сраввевая н методак сортировка ввскодяяая поразрядная сортировка. Основана аа опвсаввв, првведеавом в *Л1дог)гьнв гп с Воьегг сравневвем. Этот оператор заполняет все преобразовааая, веобкоданме для располопеввя батов в Яеддет)св. 15ВИ:0-201-31452-5. порядке вх заачвмоств. Здесь бнл введен оператор СВОИК, авалогвчанй оператору сраваевая в методах сортаровка В йуахппв тапке прасутствует оператор СИОИКБ, которнй одаовремевво перестраввает батя всек сраввеавем.
Этот оператор заполняет все преобразовавая, веобкодамне для располопення битов в даавмк в порядке вк звачвмоств. порядке пх звачамоств. е/ */ хоза Вдвтдвво(Игура а[), 1овд 1, 1опд г, вгке Е Веуа1ке) 41тадет Ваотк И1001ИС ( 'вг 1, (йеййпе Ьгп 1+сопле(й) 3 мз Организация данниз 6Ш !— Часть й Мстоди бв строй сортировни Глава (3 Методы сортировки слиянием за с ~ст этом уменьшить количество сравнений. Можно Листинг 13.7. Сортировка слиянием.
попробовать за счет хитроумных операций с памятью /» Предположим, мы не можем поместить все ланные в снизить потребности в дополнительной памяти до не- '* лрвведеввне нике фуикави реализует аеэффектввамй, ао поиятвнй метод двоичного слвяввя. Ен *в память, как бы ни старались. В таколз случае придется которого постоянного значения. Но полученный в репроводзпь сортировку по частям, а затем соединять от- зультате всех эзих ухигцрений алгоритм будет все равто[й дельные части в единое целое. /[ля этого используется но луже метода быстрой сортировки.
ЕНЕКОЕ (Екуре Л(), Есуре В[), а1ае Е 1, азае Е в, азае Е г) мстолика. которая называется слиянием ( /)ля понимания принципа слияния сначата рассмот- СОртиРОВКЗ СЛИЯНИЕМ С ДЕЛЕНИ6М НВ ьзае Е 1 1; рилз простой пример, а затем приведем пару примеров СЕКЦИИ взае 1 ) = в в 1] озве Е К = 1; использования этого принципа.
В качестве основного /1 сейчас лапайте поговорим о потоке ланныл. Какими /* Вставать миввмальвнй элемеат в массив В */ метода сортировки наборов данных любо~о размера для нй11е ((з <= в) ьь (1 <и т)) слияния о ельных наборов д ных бу11ем пользе ь- сво ств' зон балласт'. И' стно,ч усвоиствами он обладает? Известно, что значения посту( ся очередью по приоритету. паюших лап ных либо увеличиваются, либо уменьшаютьй (Ьт (Л[з), В[1[)) ся, либо остаются постоянными.
Эго называется три- В[КВ+) " а[1++)1 Сортировка двоичным слиянием хонюмией (хорошее слово для тех, кто сто узко знает). е1ае Как бы там ни было, предположим, что сначала мы посСамым пйостым лла пониманпЯ ЯюзЯетсЯ лвоичное сли- ро и ем все данные Пока данные ) /* Скопировать остаток (если таковой есть) */ ирис (слияние лвух наборов ланных, которос иногла н меняю на рагл ние своего изм пения (постоянно е.' т пр зс ий11е (з <и в) увеличиваются или уменьшаются), вносим их в зеку- ( таз)у[.' Мет Поскольку данные сортируются отдельными блока- ял требуют много памяти.
Необходимо отмечать нача- Листинг 13.8. Алгоритм слияния с делением нв секции. ми (все ланные не помещаются в памяти), у нас будет ло и конец каждой секции и указывать. какая это сексписок файлов, в которых булут солсржаться отсорти- ция: возрастающая или убывающая. Скорее всего, эти Даавая фуакцая предаазаачеаа дпя разбивки дааавх аа секции. рованныс блоки. Если поместить я очередь по приори- данные будут состоять из двух значений типа цвз)двед е* Это ковечааа автОМат с двумЯ сОстояааяяа.
Возраставваа секцая — 1, убивавпая сехцая — О. гегам все списки в возрастающем порядке, а затем вы- [оцй и одного значения типа сйаг. Если ключи имеют ь* так ввгпядат заачвтепьао усовераеаствоваааая версия моего кода. Вопьвая часть бирать верхний элемент очерели до тех пор, пока она малую ллину, то вспомогательные ланные будут зани- '* уссвервеаствовавай ваесеаа Хааг Су Гатлваои (хаил зп Оаг1[п).
не станет пустой, то мы отсортируем всс элементы за мать слишком много памяти. И это еше не все — при я/ олин этап. "Произошло чудоГ' — закричитс яы (надеюсь, малых размерах секций наш алгоритм велет себя как 1ПГ РЛДОСДВ(ВГУРа Я аттаУ, Пазсчаац 1ОПО П, Ракесе[ОЛ Ра[), 1ОПО ВаХ Рат) нс вслух). Способ, предусматривающий работу с очере- обычная пирамидальная сортировка. А мы уже знаем, ( дью по приоритетам, и способ слияния двух списков в что пирамидальная сортировка в среднем намного хуже цпаучпед 1опл 1[ основном аназогичны, но имеют существенное отличие. быстрой сортировки.
бугесглоп[ 1опч рсоппе = О; При одновременной сортировке двух списков, которые не помещаются в памяти, придется постоянна расютать СОртИрОВКа О)ИЯНИЕМ ПО ПрИНцИПу с диском. При использовании очсрели по приоритетам иНЯРОЗЯНИЯ ПЯЧЯНЬЯ рь[рсоппс[.аясепвупц = цл(актау[ 1), аггау[О))' мы будем делать следующее. Гог (1 = 1[ з < и; 1++) ( Лля решения именно этой проблемы предлагается но- д1гесг(оп = сщаггау(з), актау[1 — 1)); Алгоритм со тиривки слиянием с делением на секции, вый метод, который нвзвывается "нарезанис печенья" гб (ря(рсоппг).аясепдзпл 1= д(гесе1оп) ( (соо)с)е-сццег). Предположим, мы начинаем сканирова- рсоппг+е; [.
Сканируя данные или открывая уже упорядоченныс ние ланных, и по результатам предварительного анали- (рсоцпс > вах раг) последовательности, записанные на лиске, форми- за узнаем, что данные будут разбиты на слишком боль- гегпгп -вах аг; Органиэации данных Мтноды быгтрои сортиров и Глава 13 Часть Н е1ае Ьед = ++1рд) ) геспгп е; ) а ве с эпеиеатамв данных вгхе С сонат, Втуре * Ната) 1( (р.авсепб1пд) ( е = йаса[р.асагс]; ) е1ве ( е = цапа[р.впав]1 /1 ** Этот метод Велла работает с сехцвямв дааннх */ иохй РННВЬЬЯОВт(рагс11)оп аггау[) ( ] /и Предоставвть место в даса[1рд] для бага[О[ */ /* Сохранять новый элемент, который мы собираемся вставать *! (ог (1 = О; 1 < 1Рд; 1о+) аггау[1] = аггау[ 1 + 1); аггау[ грд - 1] = Гевр; /* Вставить воней элемент в вувное место */ гецогп; агхе с /и этот метод сортвровхн спвяавем монна назвать попезанм.
Во реальной ценвостьв обладает верона с операцвямн ввода/вывода */ тохй ИВВСВ ЯОВт( 1, 1ПС опн1дпед 1опд соопт, рагс)с[оп ' рэег, ппайдпед 1опд шах раг сыр[ есвр Всуре а[], рагг111оп птурс (ог (гпс = сооп11 1пс > О;) ( ) уог (1 = (по[ 1 < сонат; 1++) 1опд Органнзтяня данныи 1 Часть!1 оритмы сортировки -еизаод'!!»гиги.гг. а иаг ра си ьгз ы ! ' ! ' ! ! 50Й,()ьй - —" — ' уИОВМа511Е(реев, рсоппп, а)т ) петеру(а, а11екпапе, поппе * в1вео((ппуре))т (кее(а1пекпапе)т ) е1ее 1()ЯОа15(аг СОППК)Г Г' ° Кпепц уСтОйЧИВОГО аЕЕОда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
