Skip to content

Instantly share code, notes, and snippets.

@notaLonelyDay

notaLonelyDay/FilesMergeSort.pas

Last active May 5, 2021 12:44
Show Gist options
  • Save notaLonelyDay/d0920ea5c4fcb1365955e714f67cb87e to your computer and use it in GitHub Desktop.
Save notaLonelyDay/d0920ea5c4fcb1365955e714f67cb87e to your computer and use it in GitHub Desktop.
Download ZIP
MergeSort
Raw
FilesMergeSort.pas
// written by github.com/notaLonelyDay
program MergeSortConsole;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils;
const
RANDOM_MAX = 100;
MAIN_FILENAME = 'int_file';
HELPER1_FILENAME = 'helper_file_1';
HELPER2_FILENAME = 'helper_file_2';
type
TTypedIntFile = File of Integer;
var
MainFile, Helper1, Helper2: TTypedIntFile;
i, t, j: Integer;
procedure createRandomIntTypedFile(filename: String; size: Integer);
var
f: TTypedIntFile;
i, rnd: Integer;
begin
AssignFile(f, filename);
Rewrite(f);
for i := 1 to size do
begin
rnd := Random(RANDOM_MAX);
Write(f, rnd);
end;
Writeln;
Close(f);
end;
procedure writeMainFile;
begin
Reset(MainFile);
for i := 1 to Filesize(MainFile) do
begin
Read(MainFile, t);
Write(t, ' ');
end;
Writeln;
Reset(MainFile);
end;
procedure mergeSortFile(var f, h1, h2: TTypedIntFile);
var
fSize, pairSize: Integer;
h1Size: Integer;
h2Size: Integer;
i: Integer;
temp, helper1Pointer, helper2Pointer, inPair1Pointer, inPair2Pointer,
splitPointer: Integer;
cache1, cache2: Integer;
begin
pairSize := 1;
fSize := Filesize(f);
while (pairSize < fSize) do
begin
//writeMainFile;
// splitting
Reset(f);
Rewrite(h1);
Rewrite(h2);
splitPointer := 0;
// Делим главный файл в два вспамогательных
while (splitPointer < fSize) do
begin
i := 0;
while (splitPointer < fSize) and (i < pairSize) do
begin
read(f, temp);
write(h1, temp);
inc(i);
inc(splitPointer);
end;
i := 0;
while (splitPointer < fSize) and (i < pairSize) do
begin
read(f, temp);
write(h2, temp);
inc(i);
inc(splitPointer);
end;
end;
Reset(h1);
Reset(h2);
Rewrite(f);
h1Size := Filesize(h1);
h2Size := Filesize(h2);
// updating caches
Read(h1, cache1);
Read(h2, cache2);
// merging
helper1Pointer := 0;
helper2Pointer := 0;
while (helper1Pointer < h1Size) and (helper2Pointer < h2Size) do
begin
inPair1Pointer := 0;
inPair2Pointer := 0;
// Слили все пары для которых совместные пары
while (helper1Pointer < h1Size) and (helper2Pointer < h2Size) and
(inPair1Pointer < pairSize) and (inPair2Pointer < pairSize) do
begin
if (cache1 < cache2) then
begin
Write(f, cache1);
inc(helper1Pointer);
inc(inPair1Pointer);
if not eof(h1) then
Read(h1, cache1);
end
else
begin
Write(f, cache2);
inc(helper2Pointer);
inc(inPair2Pointer);
if not eof(h2) then
Read(h2, cache2);
end;
end;
while (helper1Pointer < h1Size) and (inPair1Pointer < pairSize) do
begin
Write(f, cache1);
inc(helper1Pointer);
inc(inPair1Pointer);
if not eof(h1) then
Read(h1, cache1);
end;
while (helper2Pointer < h2Size) and (inPair2Pointer < pairSize) do
begin
Write(f, cache2);
inc(helper2Pointer);
inc(inPair2Pointer);
if not eof(h2) then
Read(h2, cache2);
end;
end;
while (helper1Pointer < h1Size) do
begin
Write(f, cache1);
inc(helper1Pointer);
if not eof(h1) then
Read(h1, cache1);
end;
while (helper2Pointer < h2Size) do
begin
Write(f, cache2);
inc(helper2Pointer);
if not eof(h2) then
Read(h2, cache2);
end;
pairSize := pairSize * 2;
end;
end;
procedure test;
var
prev, cur: Integer;
begin
Reset(MainFile);
Read(MainFile, prev);
for i := 2 to Filesize(MainFile) do
begin
Read(MainFile, cur);
if (cur < prev) then
begin
Writeln('Error!');
Exit;
end;
prev := cur;
end;
Writeln('OK!');
Writeln('Test passed!');
end;
begin
for j := 1 to 100000 do
begin
Writeln(j);
createRandomIntTypedFile('int_file', 1);
// Exit;
AssignFile(MainFile, MAIN_FILENAME);
Reset(MainFile);
AssignFile(Helper1, HELPER1_FILENAME);
Rewrite(Helper1);
AssignFile(Helper2, HELPER2_FILENAME);
Rewrite(Helper2);
// Reset(MainFile);
// for i := 1 to Filesize(MainFile) do
// begin
// Read(MainFile, t);
// Write(t, ' ');
// end;
// writeln;
// Reset(MainFile);
mergeSortFile(MainFile, Helper1, Helper2);
test;
end;
Readln;
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment