Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
procedure Copy ⇐ ПредыдущаяСтр 2 из 2
begin y.Elem: =self.Elem; write(y.f, y.Elem); f.eof: =sustem.eof(f); if not f.eof then read(f, f.elem); f.eor: =f.eof or (f.elem< y.elem); end;
Многофазная сортировка. сначала происходит начальное распределение данных, а затем используется (N— 1)-путевое слияние, то есть все время серии берутся из N — 1 файлов и сливаются в один пустой. Чтобы (N — 1)-путевое слияние стало возможным, необходимо вначале распределить данные особым образом: распределение происходит на N — 1 вспомогательный файл, при этом количество серий в каждом из файлов зависит от количества вспомогательных файлов и количества серий в исходном файле. Поскольку последний параметр заранее не известен, то распределение серий происходит по уровням. Если в исходном файле одна серия, то на нулевом уровне все данные должны быть записаны в один файл. На всех остальных уровнях количество серий, которое должно быть распределено на каждый из вспомогательных файлов, определяется формулами:
где L — номер уровня, а N — количество вспомогательных файлов. Нетрудно заметить, что количество серий в исходном файле может отличаться от такого идеального распределения. В этом случае считается, что в распоряжении имеются фиктивные (пустые) серии, причем их столько, что сумма пустых и реальных серий равна идеальной сумме. Заметим, что слияние пустых серий из всех N — 1источников означает, что никакого реального слияния не происходит, вместо него в выходную последовательность записывается результирующая пустая серия. Отсюда можно заключить, что пустые серии нужно как можно более равномерно распределять по N — 1последовательностям. Алгоритм " горизонтального распределения пустых серий", позволяет эффективно распределить серии. 1. Подсчитать число серий, которое должно быть распределено в каждый из вспомогательных файлов на данном уровне (aiL i = 1,..., N — 1). 2.Подсчитать количество серий, которое надо дописать в каждый из вспомогательных файлов на данном уровне, чтобы получить число серий, равное aiL: diL = aiL - aiL- 1. После того как это число определено, считаем, что в каждый из вспомогательных файлов записано diL пустых серий. 3. Пока не кончился исходный файл и пока не исчерпаны все пустые серии на данном уровне, заменяем пустую серию на реальную; при этом записываем ее в тот файл, в котором количество пустых серий максимально. 4. Если исходный файл не кончился, осуществляется переход на следующий уровень: L = L + 1 и переход к пункту 1. Когда все данные распределены, происходит слияние данных: сначала сливаются данные из вспомогательных файлов с номерами 1, 2,..., N — 1 в N- ыйвспомогательный файл, при этом файл с номером N— 1 станет пустым (слияние на L- омуровне). Далее номер уровня уменьшается и происходит слияние файлов с номерами 1, 2,..., N — 1 в (N — 1)-ый файл, т. е. слияние на L — 1 уровне. Так продолжается до тех пор, пока номер уровня не станет равным 0. Заметим, что во время слияния на очередном уровне, если не кончились пустые серии, то в первую очередь объединяются они, поскольку их объединение требует меньше затрат.
Procedure Select (номер файла, куда пойдет запись реальной серии) Var I, z: integer; Begin If d[j]< d[j+1] then inc(j) Else begin If d[j]= 0 then begin \\ нет фиктивн серий Level: =level+1; Z: =a[1]; For i: =1 to N-1 do begin D[i]: =z+a[i+1]-a[i]; A[i]: =z+a[i+1]; end; end; J: =1; end; D[j]: =d[j]-1; end; BEGIN F0: =TSequance.Create (‘1.tmmp’); For i: = 1 to N do F[j]: =TSequance.Create (IntToStr(i)+’.tmp’) Level: =1; For i: =1 to n-1 do begin A[i]: =1; d[i]: =1; F[i].startWrite; end; A[n]: =0; d[n]: =0; F0.startRead; j: =1; \\ куда пишем серию Repeat Select; f0.CopyRun(f[j]); Until f0.eof or (j=n-1); While not f0.eof do begin Select; If f[j].elem< =f0.elem then begin F0.copyrun(f[j]); If f0.eof then inc(d[j]); Else f0.copyrun(f[j]); end; Else f0.copyrun(f[j]); end; For i: =1 to n-1 do begin F[i].StartRead; t[i]: =I; end; T[n]: =n;
Repeat Z: =a[n-1]; D[n]: =0; F[t[n]].startwrite; Repeat K: =0; For i: =1 to n-1 do If d[i]> 0 then dec(d[i]) Else begin Inc(k); ta[k]: =i; end; If k=0 then \\ во всех есть фиктив серии Inc(d[n]); Else repeat i: =1; mx: =1; \\ мин в карте индексов min: =f[ta[1]]; while (i< k) do begin inc(i); x: =f[ta[i]].elem; if x< min then begin min: =x; mx: =I; end; end; f[ta[mx]].copy(f[t[n]]); if f[ta[mx]].eor then begin ta[mx]: =ta[k]; dec(k); end; until k=0; dec(z); until z=0; f[t[n]].startread; tn: =t[n]; dn: =d[n]; i: =a[n-1]; for i: = n downto 2 do begin t[i]: =t[i-1]; d[i]: =d[i-1]; a[i]: =a[i-1]-z; end;
t[1]: =tn; d[1]: =dn; a[1]: =z; f[t[n]].startwrite; level: =level-1; until level=0; f[t[1]].copyAll(f0); for i: =1 to N do begin f[i].clear; f[i].Erase; f[i].destroy; end; fo.destroy; END
Каскадная сортировка похожа на многофазную сортировку. Отличие заключается в самом процессе слияния: сначала проводится (N — 1 ) — путевое слияние в N -ый файл до тех пор, пока файл с номером N— 1 не опустеет; затем (N -ый файл уже не затрагивается) проводится (N — 2) — путевое слияние в (N— 1)-ый файл; затем (N— 3) — путевое в (N— 2)-ый файл;...; потом двухпутевое слияние в третий файл, а в конце копирование из файла с номером 2 в первый файл. Следующий проход работает по аналогичной схеме, только в обратном направлении. Поскольку слияние в каскадной сортировке отличается от слияния в многофазной сортировке, то и начальное распределение данных осуществляется по-другому — количество серий в каждом из вспомогательных файлов должно быть другим. Оно определяется в соответствии с формулами:
или
Н. Вирт пишет: " Хотя такая схема выглядит хуже многофазного слияния, поскольку некоторые последовательности " простаивают", и есть просто операции копирования, тем не менее, она, что удивительно, оказывается лучше многофазной сортировки при очень больших файлах и шести или более последовательностях". Заметим, что при хорошей реализации алгоритма каскадной сортировки, от копирования можно избавиться, используя карты индексов.
|