Solved

# External Sorting

Posted on 2004-04-12
1,686 Views
I need a simple (im sure its simple for you guys) algorithm that can sort a large textfile.

i need my program to first sort and then merge (nothing new!!) . the sorting stage would split my large textfile into several smaller  sorted textfiles and and the merging stage would merge all these textfiles together to make the final sorted textfile. i have tried it myself but i cannot figure out the algorithm ( i always get stuck at some point and realise i cannot continue).
i dont want to have to use pointers...maybe there is some recursive method ??(not sure). i have looked at swag but there doesnt seem to be anything close enough to what i need.

Any help is more than appreciated !!! :)

Thanks a real lot!

0
Question by:jwirth779

LVL 11

Expert Comment

ID: 10806063
how do you want them sorted, I mean you could sort by alphabetical, length of line, numerical?
0

Author Comment

ID: 10807596
numerical....ascending order preferably!!!
0

LVL 100

Expert Comment

ID: 10810415
Homework per chance?

mlmcc
0

Author Comment

ID: 10811723
no... why do you ask? im gonna increase the points...
0

Expert Comment

ID: 10812141
i have a program which will sort 20000 numbers (but very fast) in ascending order!! Would you like to apadpt it (my sorting program) for you to make the numbers as an input from your textfile?
0

Author Comment

ID: 10813411
yes that would be really good of you. but the thing is that i must use the sort and merge procedure that i described before (it is a technique so ill be able to sort even if i dont have enough memory - but im sure you know that already) Does your program use a sort and merge algorithm?

Thanks again for all you help!!! :)
0

Expert Comment

ID: 10813756
no it does not use merge. Do you want it without the merge algorithm (it is still very effecient - it picks up 20000 random numbers and then sorts them in an average speed of less that 4.5 seconds, i think that would be effecient enough!)
0

Author Comment

ID: 10813980
the thing is that i really need a sort and merge algorithm so ill be able to sort a textfile no matter what the size of the textfile is....
this is an exmple of my textfile :
test      01      26      test
test      02      15      test
test      03      66      test
test      04      37      test
test      05      61      test
test      06      33      test
test      07      95      test
test      08      99      test
test      09      31      test
test      10      82      test
.               .               .               .
.               .               .               .
.               .               .               .
test           500           34            test

there are 500 hundred lines.... and the second colomn of numbers are between 1-100 (colomn to be sorted!!).
preferably this textfile is split up in 10 smaller sorted files and then merged to form one large sorted file!!

any idea????

thanks guys!!
0

Expert Comment

ID: 10820813
i made a program which splits an unsorted textfile in 10 other textfiles. Sort the textfile and then create a new sorted textile!

SAMPLE INPUT IN UNSORTED TEXTFILE:

1  12
2  14
3  19
4  89
5  27
6  20
7  73
8  10
9  46
10 28
11 32
12 44
13 59
14 69
15 77
16 80
17 93
18 100
19 26
20 38

SAMPLE OUTPUT IN SORTED TEXTFILE

10
12
14
19
20
26
27
28
32
38
44
46
59
69
73
77
80
89
93
100

This is what you wanted or something similar!!! Hope i've of help. I you want it just tell me! :)
0

Author Comment

ID: 10821893
yeah that sounds great!! do you think you could pass it on to me???
0

Expert Comment

ID: 10821933
it is a little bit long! do you have an email so i can send it to? Otherwise i write it for you
0

Accepted Solution

alandemartino earned 400 total points
ID: 10821944
Here it is: Hope you like it!!!

uses crt;
const
max        =  20;
var
filename,pos,t,tsrt : string;
userfile     : text;
num          : array [1..max] of integer;
snum         : array [1..max] of string;
i,x,v,code,tnum,c,srt   : integer;
loops                   :real;
begin
clrscr;
filename:='C:/unsorted';
Assign(userfile,filename+'.txt');
Reset(userfile);
i:=1;
Repeat
inc(i);
Until (eof(userfile));
i:=1;
srt:=0;

for i := 1 to max do         {splits into 10 more textfiles}
begin
inc(srt);
if (srt > 10) and (srt = 11)then
srt:=1;
if i > 10 then
begin
str(srt,tsrt);
filename:='C:/sort'+tsrt;
Assign(userfile,filename+'.txt');  { Standard output }
append(userfile);
Writeln(userfile,snum[i]);
close(userfile);
end
else
begin
str(srt,tsrt);
filename:='C:/sort'+tsrt;
Assign(userfile,filename+'.txt');  { Standard output }
Rewrite(userfile);
Writeln(userfile,snum[i]);
close(userfile);
end;
end;

x:=0;
i:=1;
repeat
inc(x);
pos:=copy(snum[i],x,1);
until pos = ' ';

while pos =  ' ' do
begin
pos:=copy(snum[i],x+1,1);
inc(x);
end;

v:=1;

for i := 1 to max do
begin
t:=copy(snum[i],x,2+v);
val(t,num[i],code);
end;

i:=0;
repeat
inc(i);
if i = max then
begin
i:=1;
inc(c);
end;

if num[i] > num[i+1] then
begin
tnum:=num[i];
num[i]:=num[i+1];
num[i+1]:=tnum;
end;
until ( c = max-2);

filename:='C:/sortedfile';
Assign(userfile,filename+'.txt');
Rewrite(userfile);
for i := 1 to max do
Writeln(userfile,num[i]);
close(userfile);

end.
0

Author Comment

ID: 10823350
it looks real good...thx alot....im gonna go over it and then give you the points.... cheers mate.
0

Expert Comment

ID: 10824355
no problem man!!!!!
0

Expert Comment

ID: 10836244
Did it work!!
0

Author Comment

ID: 10836665
yeah it works ok

im just having abit of a problem adapting it to for example 500 records... its more than good enough though...thanks alot!!!

i might have a couple of problems still.... if you want ill give you the points anyway!!
0

Expert Comment

ID: 10839624
I appreciate it very much. :)
0

Author Comment

ID: 10843123
im having a problem to modify it to 1000 records for example....how come?
0

Author Comment

ID: 10843296
ok sorted!! cheers...

all yours!
0

Expert Comment

ID: 10843755
Thank you very much, and by the way if you need anymore help,  as long as i know i will help you
0

## Featured Post

### Suggested Solutions

Short answer to this question: there is no effective WiFi manager in iOS devices as seen in Windows WiFi or Macbook OSx WiFi management, but this article will try and provide some amicable solutions to better suite your needs.
Is your Office 365 signature not working the way you want it to? Are signature updates taking up too much of your time? Let's run through the most common problems that an IT administrator can encounter when dealing with Office 365 email signatures.
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files â€” any plâ€¦
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: â€¦