U Diksa i Ryttera znalazlem taki pseudokod
Jak zapisac go w wybranym jezyku programowania
Załóżmy że bloki zostały rozłożone na pliki P_{0} i P_{1} Pliki P_{2} i P{3} są początkowo puste
i_{1}:=0; i_{2}:=1; {numery plików wejściowych , tzn. otwartych do czytania}
j_{1}:=2; j_{2}:=3; {numery plików wyjściowych , tzn. otwartych do pisania}
while (jest wiecej niz jeden blok) do
(a) scal pierwszy blok na P_{i_1} z pierwszym blokiem na P_{i_2} i powstający blok
zapisz na P_{j_1}
(b) scal następny blok na P_{i_1} z następnym blokiem na P_{i_2} i powstający blok
zapisz na P_{j_2}
(c) powtarzaj kroki (a) i (b) (kładąc powstające bloki na przemian na pliki P_{j_1} i P_{j_2}),
aż zostanie osiągnięty koniec plików P_{i_{1}} i P_{i_{2}}
(d) przewiń wszystkie pliki do początku;dodaj liczbę 2 mod 4 do i_{1}, i_{2}, j_{1},j_{2}
odwracając w ten sposób rolę plików wejściowych i wyjściowych
Rozdzielenie blokow z pliku zrodlowego na pliki P0 i P1 mogloby wygladac np tak;
uses crt;
const maxA=128;
type TElem=string;
TArray=array[1..maxA]of TElem;
procedure heapify(var A:TArray;p,heapsize:integer);
var left,right,largest:integer;
isHeap:boolean;
temp:TElem;
begin
isHeap:=false;
while((p<=heapsize)and(not isHeap))do
begin
left:=2*p;
right:=2*p+1;
if((left<=heapsize)and(A[left]>A[p]))then
largest:=left
else
largest:=p;
if((right<=heapsize)and(A[right]>A[largest]))then
largest:=right;
if(largest<>p)then
begin
temp:=A[largest];
A[largest]:=A[p];
A[p]:=temp;
p:=largest;
end
else
isHeap:=true;
end;
end;
procedure heapSort(var A:TArray;n:integer);
var i:integer;
temp:TElem;
begin
for i:=n div 2 downto 1 do
heapify(A,i,n);
for i:=n downto 2 do
begin
temp:=A[1];
A[1]:=A[i];
A[i]:=temp;
heapify(A,1,i-1);
end;
end;
procedure createBlocks(var A:TArray;var f:text;var f0:text;var f1:text);
var i,j,k:integer;
begin
reset(f);
rewrite(f1);
rewrite(f2);
j:=0;
k:=0;
while not eof(f)do
begin
j:=j+1;
readln(f,A[j]);
if(j=maxA)or eof(f) then
begin
heapSort(A,j);
if(k=0)then
for i:=1 to j do
writeln(f0,A[i]);
if(k=1)then
for i:=1 to j do
writeln(f1,A[i]);
j:=0;
k:=(k+1)mod 2;
end;
end;
close(f);
close(f1);
close(f2)
end;
var A:TArray;
sourceFile:text;
tempFiles:array[0..3]of text;
sourcePath:string;
begin
clrscr;
write('Enter source file path: ');
readln(sourcePath);
assign(sourceFile,sourcePath);
assign(tempFiles[0],'in001.txt');
assign(tempFiles[1],'in002.txt');
assign(tempFiles[2],'out001.txt');
assign(tempFiles[3],'out002.txt');
createBlocks(A,sourcefile,tempFiles[0],tempFiles[1]);
end.
Znalazlem u pewnago kolesia sortowanie przez laczenie proste
uses crt;
procedure Split(partLength:longint;var inFile:text;var auxFileOne:text;var auxFileTwo:text);
var buffer:string;
counter:longint;
begin
repeat
counter:=1;
while((counter<=partLength)and(not eof(inFile)))do
begin
readln(inFile,buffer);
writeln(auxFileOne,buffer);
counter:=counter+1;
end;
counter:=1;
while((counter<=partLength)and(not eof(inFile)))do
begin
readln(inFile,buffer);
writeln(auxFileTwo,buffer);
counter:=counter+1;
end;
until eof(inFile);
end;
procedure combine(partLength:longint;var auxFileOne:text;var auxFileTwo:text;var inputFile:text);
var bufferOne,bufferTwo:string;
counterOne,counterTwo:longint;
begin
if(eof(auxFileOne)=false)then
readln(auxFileOne,bufferOne);
if(eof(auxFileTwo)=false)then
readln(auxFileTwo,bufferTwo);
while((eof(auxFileOne)=false)and(eof(auxFileTwo)=false))do
begin
counterOne:=1;
counterTwo:=1;
repeat
if(bufferOne<bufferTwo)then
begin
writeln(inputFile,bufferOne);
if(eof(auxFileOne)=false)then
readln(auxFileOne,bufferOne);
counterOne:=counterOne+1;
end
else
begin
writeln(inputFile,bufferTwo);
if(eof(auxFileTwo)=false)then
readln(auxFileTwo,bufferTwo);
counterTwo:=counterTwo+1;
end;
until not((counterOne<=partLength)and(counterTwo<=partLength)and(eof(auxFileOne)=false)and(eof(auxFileTwo)=false));
while((counterOne<=partLength)and(eof(auxFileOne)=false))do
begin
readln(auxFileOne,bufferOne);
writeln(inputFile,bufferOne);
counterOne:=counterOne+1;
end;
while((counterTwo<=partLength)and(eof(auxFileTwo)=false))do
begin
readln(auxFileTwo,bufferTwo);
writeln(inputFile,bufferTwo);
counterTwo:=counterTwo+1;
end;
end;
while(eof(auxFileOne)=false)do
begin
readln(auxFileOne,bufferOne);
writeln(inputFile,bufferOne);
end;
while(eof(auxFileTwo)=false)do
begin
readln(auxFileTwo,bufferTwo);
writeln(inputFile,bufferTwo);
end;
end;
var partLength:longint;
exitCond:boolean;
inputFile,auxFileOne,auxFileTwo:text;
inputFileName:string;
begin
clrscr;
partlength:=1;
exitCond:=false;
writeln('Enter path to file');
readln(inputFileName);
assign(inputFile,inputFileName);
assign(auxFileOne,'out001.txt');
assign(auxFileTwo,'out.002.txt');
repeat
reset(inputFile);
rewrite(auxFileOne);
rewrite(auxFileTwo);
split(partlength,inputFile,auxFileOne,auxFileTwo);
close(auxFileOne);
close(auxFileTwo);
close(inputFile);
rewrite(inputFile);
reset(auxFileOne);
reset(auxFileTwo);
if(not eof(auxFileTwo))then
begin
combine(partlength,auxFileOne,auxFileTwo,inputFile);
partLength:=2*partLength;
end
else
exitCond:=true;
close(auxFileTwo);
close(auxFileOne);
close(inputFile);
until (exitCond=true);
end.
ale nie wydaje mi się aby poprawnie laczyl pliki
Oryginal jest w pliku pdf
http://ww2.ii.uj.edu.pl/~kawa/epi/asd/materialy/Algorytmy%20i%20struktury%20danych.pdf