Внешняя многофазовая сортировка слиянием...

[maLoy*508]

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

[alexBlack]

Д.Кнут 3 том. стр. 294

[maLoy*508]

спасибо... выручил

[maLoy*508]

а может мне кто по простому объяснит..
а то что то тяжеловато до меня доходит...
заранее спасибо

[alexBlack]

Сообщение от maLoy*508

а может мне кто по простому объяснит..
а то что то тяжеловато до меня доходит...
заранее спасибо

А конкретней, какой момент непонятен ? Если не самые сложные моменты, то:
По простому. Сбалансированное двухпутевое слияние. Отсортированные серии делим на два файла:

[0-1][2-3][4-5]
[1-2][3-4]

Слиянием этих файлов получаем 3-й

из [0-1],[1-2] - [a-b]
из [2-3],[3-4] - [b-c]
[4-5] просто копируем [4-5]
получили [a-b][b-c][4-5]

Этот файл снова делим на два файла

[a-b][4-5]
[b-c]

и мы опятьна шаге 1, но серий стало меньше. Когда останется одна серия, сортировка закончена.

Многофазная сортировка - одно небольшое изменение. Третий файл делим на два по-другому. Половину оставляем в этом файле, вторую половину копируем. Снова получаем два файла (3, 1) 2-й используем для слияния. Поэтому многофазная - файлы меняются местами.

Остальное описание - многопутевая сортировка и тонкости выбора серий. С учетом этого описания перечитайте еще раз главы Кнута. Надеюсь станет понятно.
-------------------------------------
Это только мое понимание прочитанного. В тонкости не вникал и реализовать не пробовал.

[maLoy*508]

сам алгоритм понял, точнее нашел готовый... книга Дж. Макконела помогла...
Но алгоритм алгоритмом. Попробывал релизовать, застрял на том, что не могу считать отрезки

вот алгоритм, это первая часть, которая разбивает исходный файл на два, состоящих из отсортированных отрезков
CreateRuns(S)
S размер создаваемых отрезков
CurrentFile=A
while конец входного файла не достигнут do
read S записей из входного файла
sort S записей
if CurrentFile=A then
CurrentFile=B
else
CurrrentFile=A
end if
end while

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

ну а это второй этап(до которого я еще не добрался)
PolyPhaseMerge(S)
S размер исходных отрезков
Size=S
Input1=A
Input2=B
Current Output=C
while not done do
while отрезки не кончились do
слить отрезок длины Size из файла Input1
с отрезком длины Size из файла Input2
записав результат в CurrentOutput
if (CurrentOutput=A) then
CurrentOutput=B
elsif (CurrentOutput=B) then
CurrrentOutput=A
elsif (CurrentOutput=C) then
Currrent Output=D
elsif (CurrentOutput=D) then
CurrrentOutput=C
end if
end while
Size=Size*2
if (Input1=A) then
Input1=C
Input2=D
Current Output=A
else
Input1=A
Input2=B
CurrentOutput=C
end if
end while

[alexBlack]

Сообщение от maLoy*508

...Попробывал релизовать, застрял на том, что не могу считать отрезки
...
не могу понять как их считывать, точнее допустим читаем в массив по десять элементов, в самом файле всех элементов 35, как поступать с последними пятью элементами.

- можно просто запомнить, что последняя серия неполная (запомнить ее размер) и при слиянии серий это учитывать.

- можно дополнить ее до размера серии байтами $FF, а после слияния эту часть отбросить.

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

Какой-тип файла, как Вы пишете и что ожидаете там увидеть ?

[maLoy*508]

Я не знаю размер файла, так что запомнить не получиться...
....
const
n=10;
type
op=array [1..n] of integer;
....
var
ar : op;
file1:file of integer;
fileA:file of op;
begin
assignfile(fileA,'a.txt');
assignfile(file1,ExtractFileName(Op enDialog1.FileName));
reset(File1);
reset(FileA);
while not eof(file1) do
begin
for i:=1 to n do read(file1,ar[i]);
bubblesort(ar);
write(filea,ar);
end;
...
...

[alexBlack]

Сообщение от maLoy*508

Я не знаю размер файла, так что запомнить не получится...
...

У Вас процесс чтения неправильно организован. Нужно

N := 0
while not eof(file1) do begin
    inc(N);
    read(file1,ar[N]);

    if N = 10 then begin
       // Здесь набрался полный блок
       // его можно сортировать и записать 

       ....

       N := 0;
    end;
end;
if N > 0 then begin
  // А вот здесь остаток - часть блока длиной N 
 
  ...
end;

Есть еще BlockRead
А в Delphi проще пользоваться TFileStream

[maLoy*508]

А в Delphi проще пользоваться TFileStream

А по подробней можно пожалуйста