Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 22
Текст из файла (страница 22)
К сожалению, как может заметить внимательный читатель, эта программа некорректна, поскольку в некоторых случаях она неправильно производит сортировку. Рассмотрим, например, такую последовательность входных данных: 3 2 5 11 7 13 19 17 23 31 29 37 43 4! 47 59 57 61 71 67 Распределяя последовательные серии поочередно в файлы а и Ь, мы получим а = 3 ' 7 13 19 ' 29 37 43 ' 57 61 71 ' Ь = 2 5 11 ' 17 23 31 ' 41 47 59 ' 67 !!9 2.8. Сортировка последовательном грайлов водит к ошибочному поведению программы, он показывает, что простое распределение серий в несколько файлов может дать в результате меньшее число выходных серий, чем входных.
Это происходит потому, что первый элемент (1+2)-й серии ыожет быть больше, чем последний элемент Ьй серии, что приведет к автоматическому слиянию двух серий в одну, Хотя и предполагается, что процедура с()з!г!Ьи!в посылает серии поровну в оба файла, действительные количества выходных серий в и и Ь могут значительно различаться. Однако наша процедура будет только сливать пары серий и заканчиваться, как только будет прочитан файл Ь, теряя при этом остаток одного из файлов. Рассмотрим такие исходные данные, которые сортнруются (и усекаются) за два последовательных прохода: Таблииа 2.!2.
Неправильный реаультат работы программы сортировии слиянием 17 19 13 57 23 29 11 59 31 37 7 61 41 43 5 67 47 71 2 3 13 !7 19 23 29 31 37 41 43 47 57 71 11 59 И 13 17 19 23 29 31 37 41 43 47 57 59 71 Эта ошибка типична для многих ситуаций. Она вызвана тем, что упускается пз виду одно пз возмо ьпых последствий, казалось бы, простой операции. Она также типична в том смысле, что существует несколько спосооов ее исправления и нужно выбрать один из пих.
Часто имеются две возможности, различие между которыми носит принципиальный характер; 1. Ь(ы видим, что операция распределения написана некорректно и не удовлетворяет требованию, чтобы число серий на двух лентах было одинаковым (илп различалось не более чем на 1). Придерживаемся принятой ранее схемы и соответствующим образом исправляем неправильную процедуру. 2. Мы видим, чго исправление неправильно написанной части гребует серьезных модификаций, н ищем способы изменить другие части алгоритма, чтобы повлиять на работу некорректной части.
Вообще говоря, первый способ выглядит более понятным и надежным, а также более честным; он в достаточной мере свободен от непредусмотренных последствий и сложных побочных эффектов. Следовательно, это тот путь, который обычно рекомендуется. Однако надо указать, что бывают случаи, когда не следует пренебрегать второй возможностью. Поэтому ниже мы покажем на этом примере, как можно исправить ошибку, пгавгазв тегкезогг (1ириг, оигриг)1 (З-ленточная, 2-ВЗазная сортировка .и ж.пгеенним гуре йет гееогй «еу.
'тгейег (прочие поля) епй; Фаре = 6ФеоФ'йет; чаг с: гире;,и: тгекег; Ьиг: йет; ргоеейаге 1и1 (чае~": Фаре); чаг х: йет; Ьев(в гезег(1'); згФФФФе -~ео1'(1') йо Ьев(в геайЦсх); Фчгйе(оигрий х.Аеу) епй; майе(п епй (йзг) 1 угвсейаге ггагиго1гпегег; чаг 1: 1пгеяег; [число сливаемых серий) еог: Ьоо!еап; (индикатор конца серии) а,Ь: !аре; ргаеейвге сору(чаг х,у: Фаре); чаг Ьи1: йет; Ьеат геаг((х, ЬиД; нтйе(ч,ЬиХ)$ 1Ф еоЯх) Фйеп еог,"=- ггие еФзе еог:= Ьиу.йеу .- епй; рикейвге соругип (чаг х,у: Фаре); Ъев!п (перепись одной серии из х в у) гереаФ сору(х,у) ввгв со~ епй; ргосейвге г(1зй 1Ьи1е; Ьерп (из с в а. и Ь) гереаФ соруччт (с,а),' ФŠ—.ео /(г) Фвеп сод'гин (с,Ь) пвй( сонг) еай , ргосейаге телегин; Ьейва (из а и Ь в с) гереаг ФФа',.Ьсу -:: Ь;.йеу Фйеп Ьерв сору (а,с); К еог Фйев соручип (Ь,с) .епй е1»е Ъев(в сору (Ь,с); слпчннем] 2.8.
Сортировка лоследователвиыв файлов К сог йеп сорухтт (а,с) еп4 юпй саг епй; ргюсеююге птсгйс; Ьсд1п (из и и Ь в с) мИе —,еоЕ(а) тт,,соЕ(Ь) йо !тех(п и!с!Ос!а!!; Е:= Е-'-1 епю; ттИе —,соЕ(а) йо Ьеа1п сорггиа (а,с); Е;= ! '-1 епд; твИе —,соЕ(Ь) до Ьее)п горгп!л (Ь,с); Е:=- Е-,'-1 еы; ЕЕл! (с1 епй; Ьее)п гереаФ гстггтгт(а\, гсжпгс(Ь); гете!(с); !!Ел!! ЕЬ!тгс; гтмсг(а); !'слсЕ(Ь); гситйс(с); Е:== О; птсгес; юпй Е =- 1 епй; Ьее(п (основная программа; чтение входной последовательности с О в конце) гситис(с); гсатЕ(Ьи(йсу); гереаг ит(гс(сЬ!тг); гсайЬа)йст) юп61 Ьиу',Ьсг =-- О: Ей! (с); па!ига!те!хе Емг( ) епй . Программа Х14.
Свртвревва естественным слиянием. изменив процедуру слияния, а ие процедуру распределения, которая изначально является ошибочной, Это значит, что схему распределения мы оставляем петро. вутой, а отказываемся от требования, чтобы серии распре. делялись поровну на две ленты. В результате программа может работать неоптимальным образом. Однако в худшем варианте она сохраняет те же характеристики; кроме того, 2. Сортировка 122 случай существенно неравномерного распределения статистически крайне маловероятен. Поэтому соображения эффективности не являются серьезным аргументом против этого решения. Если требование о распределении серий поровну отменено, то процедуру слияния следует изменить таким образом, чтобы после достижения конца одного пз файлов копировался весь остаток другого файла, а не только одна серия.
Это — несложное изменение, оно намного проще, чем какое-либо изменение схемы распределения. (Мы предлагаем читателю самому убедиться в правоте этого утверждения.) Пересмотренная версия алгоритма слияния включена в окончательную программу 2.)4. 2.3.3. Сбалансированное многопутевое саванне Затраты на последовательную сортировку пропорциональны числу проходов, так как по определению на каждом проходе происходит перепись всего множества данных. Один из способов уменьшить это число — распределять серии на более чем две ленты, Слияние г серий, которые поровну распределены на М лентах, дает в результате последовательность из г/М серий. Второй проход уменьшает это число до г/Мз, а третий — до г/М', и после и проходов остается г/М" отрезков.
Итак, общее число проходов прн сортировке п элементов М-путевым слиянием й= )!ойкп~!. Поскольку на каждом проходе производится и операций переписи, общее число операций переписи в худшем случае будет М = и ~!ойл п1. В качестве следующего упражнения мы построим программу сортировки, основанной на многопутевом слиянии.
Чтобы подчеркнуть различие между этой программой и описанной выше процедурой естественного двухфазного слияния, мы определим многопутевое слияние как однофазную сбалансированную сортировку слиянием. Это означает, что па каждом проходе имеетсн равное число входных и выходных файлов, в которые поочередно распределяются следующие одна за другой серии. Прн использовании М файлов алгоритм будет основан на М/2-путевом слиянии, если считать, что М четно. Следуя принятой ранее стратегии, мы не будем заботиться о том, чтобы предотврзтпть автоматическое слияние двух соседних серий, попавших на одну лепту. Следовательно, нам приходится разрабатывать программу слияния без требования, чтобы на входных лентах содержалось строго одинаковое число серий, 2.8.
Сортировка лоеледовательнььх файлов пз В этой программе мы впервые встречаем естественное использование структуры данных, представляющей собой массив файлов. В самом деле, удивительно, насколько велико отличие этой программы от предыдущей в результате перехода от двухпутевого к многопутевому слиянию. Это происходит прежде всего потоы1, что теперь процесс слияния не может просто завершаться после того, как будет исчерпан один из входных файлов. Вместо этого нужно вести список входных файлов, которые пока активны, т, е. не исчерпаны. Другое усложнение возникает из-за необходимости переключать группы входных и выходных лент после каждого прохода.
Вначале, в дополнение к двум знакомкам нам типам ((епт и (аре, определим тип номера ленты: (арепо = 1, . У (2.33) Очевидно, что номера лент нужны, для того чтобы индексировать массив файлов. Будем считать, что исходная последовательность элементов задана переменной 10:Саре (2.34) н для сортировки мы имеем в распоряжении Ф лент, где й( четно: ): аггау[(арепо] о((аре (2.33) Для решения проблемы переключения лент рекомендуетси использовать карту ленточных индексов.
Вместо того чтобы обращаться к ленте непосредственно с помощью индекса 1, к ней адресуются через карту (, т. е. вместо ) [(] мы пишем [[([ь]], где карта определена как (: аггау[(арепо1 о(!арепо Если первоначально ([(] =-( для любого й то перекл(очинив производится просто прп гомощи обмена пар компонент карты ([1] ([пй+ 1] ( [2] л-н ( [л й + 2] ( [пй] т (]и], где пй =- п[Ъ. Следовательно, мы всегда можем считать 7[( [1]], ..., 1[([пй] ] входными лентами, а ) [([ттй+ 1]], "., [[([и]] 2. Сортировка выходными лентами.
(В дальнейшем мы будем называть [)У[у]) просто «лентой р>.) Теперь в первом приближении алгоритм можно записать следующим образом: ргосегуиге горе»ге>пего> у; тат г',у': уаре>го; Е: Еугуееег; (число роспределле>ных серий) у: аггау [уарепо) оЕ уареуго,' Ьеегп (распределение начальных серий на У [Ц... У [пй) ) у':== пй; Е:= О; гереаг И у пй тйеп у','=- у+1 е)зе у;=- 1; «перепись одного отрезка с,у О на ленту,у')»у Е:= Е+1 гвб! еоЕ(Е'О); Еог г:= 1 Ео йо уд:= у; гсреат [слияние из у [Ц...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
