Solved

External Sorting

Posted on 2004-04-12
20
1,686 Views
Last Modified: 2010-04-16
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
Comment
Question by:jwirth779
20 Comments
 
LVL 11

Expert Comment

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

Author Comment

by:jwirth779
ID: 10807596
numerical....ascending order preferably!!!
0
 
LVL 100

Expert Comment

by:mlmcc
ID: 10810415
Homework per chance?

mlmcc
0
 

Author Comment

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

Expert Comment

by:alandemartino
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

by:jwirth779
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

by:alandemartino
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

by:jwirth779
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

by:alandemartino
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

by:jwirth779
ID: 10821893
yeah that sounds great!! do you think you could pass it on to me???
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 

Expert Comment

by:alandemartino
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

by:
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
       Readln(userfile,snum[i]);
       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);

     readkey;
end.
0
 

Author Comment

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

Expert Comment

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

Expert Comment

by:alandemartino
ID: 10836244
Did it work!!
0
 

Author Comment

by:jwirth779
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

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

Author Comment

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

Author Comment

by:jwirth779
ID: 10843296
ok sorted!! cheers...


all yours!
0
 

Expert Comment

by:alandemartino
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

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

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: …

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now