Board index » delphi » Sorting typing files

Sorting typing files

To all the pascal programmerz !

Is anyone knows about a fast way to sort a typing files by some key ?
for example to sort the file exfil by key:

type
    exrec : record
                key : word;
                name : string;
            end;        

var
    exfil : file of record;

Wating for answer

Uri Hartmann
Israel

P.S. if you write the answer so please write it to my E-mail too:
hartm...@netvision.net.il

 

Re:Sorting typing files


In article <NEWTNews.6696.819749835.hartm...@TelAviv.netvision.net.il> Uri Hartmann <hartm...@netvision.net.il> writes:

Quote
>Path: newsfeed.pitt.edu!godot.cc.duq.edu!news.duke.edu!news.mathworks.com!newsfeed.internetmci.com!in1.uu.net!pipeline!psinntp!psinntp!psinntp!news.netvision.net.il!usenet
>From: Uri Hartmann <hartm...@netvision.net.il>
>Newsgroups: comp.lang.pascal.misc,comp.lang.pascal.borland
>Subject: Sorting typing files
>Date: Sat, 23 Dec 95 12:13:11 PDT
>Organization: NetVision LTD.
>Lines: 27
>Message-ID: <NEWTNews.6696.819749835.hartm...@TelAviv.netvision.net.il>
>NNTP-Posting-Host: ts3ip13.netvision.net.il
>Mime-Version: 1.0
>Content-Type: TEXT/PLAIN; charset=US-ASCII
>X-Newsreader: NEWTNews & Chameleon -- TCP/IP for MS Windows from NetManage
>Xref: newsfeed.pitt.edu comp.lang.pascal.misc:3722 comp.lang.pascal.borland:8587
>Is anyone knows about a fast way to sort a typing files by some key ?
>for example to sort the file exfil by key:
>type
>    exrec : record
>                key : word;
>                name : string;
>            end;        
>var
>    exfil : file of record;

Dear Uri,

     I assume the external file is really big, i.e. you cannot possibly hold
all of it in memory.  [If you could, then you'd read it in, and do any of a
number of internal sorts, e.g. QuickSort or HeapSort, on it].

     External sorts typically are much slower, since you have to keep reading
and writing external records.  One algorithm is the "merge sort", which works
something like the following --
     1) Split the file up into two (or more) pieces.  When doing the split,
try to create long "runs" of sorted information.  One way to do this on the
initial, first, pass is to read in as much as fits in memory, sort it, then
write it out; read in more, sort, write, etc.
     2)  Now start a "merge" phase.  Read in runs from the two (or more)
external files you just created, and merge them into longer runs.
     3)  Split the newly-created merged file, so that you can get pieces for
another merge step.  Repeat Steps 2 and 3 until you are all done.

     At each merge step, the length of the sorted pieces should at least
double (since you will be merging at least two shorter sorted pieces
together); eventually you will have a single sorted file.

     There are numerous tricks you can take to optimize this process, for
example using more than 2 files for the split/merge step, rotating which file
is the "output" file, etc.  To learn more about this algorithm, look up
"polyphase tape sort" in your library.

Bob Schor
Pascal Enthusiast

Re:Sorting typing files


In article <NEWTNews.6696.819749835.hartm...@TelAviv.netvision.net.il> Uri Hartmann <hartm...@netvision.net.il> writes:

Quote
>Path: newsfeed.pitt.edu!godot.cc.duq.edu!news.duke.edu!news.mathworks.com!newsfeed.internetmci.com!in1.uu.net!pipeline!psinntp!psinntp!psinntp!news.netvision.net.il!usenet
>From: Uri Hartmann <hartm...@netvision.net.il>
>Newsgroups: comp.lang.pascal.misc,comp.lang.pascal.borland
>Subject: Sorting typing files
>Date: Sat, 23 Dec 95 12:13:11 PDT
>Organization: NetVision LTD.
>Lines: 27
>Message-ID: <NEWTNews.6696.819749835.hartm...@TelAviv.netvision.net.il>
>NNTP-Posting-Host: ts3ip13.netvision.net.il
>Mime-Version: 1.0
>Content-Type: TEXT/PLAIN; charset=US-ASCII
>X-Newsreader: NEWTNews & Chameleon -- TCP/IP for MS Windows from NetManage
>Xref: newsfeed.pitt.edu comp.lang.pascal.misc:3722 comp.lang.pascal.borland:8587
>Is anyone knows about a fast way to sort a typing files by some key ?
>for example to sort the file exfil by key:
>type
>    exrec : record
>                key : word;
>                name : string;
>            end;        
>var
>    exfil : file of record;

Dear Uri,

     I assume the external file is really big, i.e. you cannot possibly hold
all of it in memory.  [If you could, then you'd read it in, and do any of a
number of internal sorts, e.g. QuickSort or HeapSort, on it].

     External sorts typically are much slower, since you have to keep reading
and writing external records.  One algorithm is the "merge sort", which works
something like the following --
     1) Split the file up into two (or more) pieces.  When doing the split,
try to create long "runs" of sorted information.  One way to do this on the
initial, first, pass is to read in as much as fits in memory, sort it, then
write it out; read in more, sort, write, etc.
     2)  Now start a "merge" phase.  Read in runs from the two (or more)
external files you just created, and merge them into longer runs.
     3)  Split the newly-created merged file, so that you can get pieces for
another merge step.  Repeat Steps 2 and 3 until you are all done.

     At each merge step, the length of the sorted pieces should at least
double (since you will be merging at least two shorter sorted pieces
together); eventually you will have a single sorted file.

     There are numerous tricks you can take to optimize this process, for
example using more than 2 files for the split/merge step, rotating which file
is the "output" file, etc.  To learn more about this algorithm, look up
"polyphase tape sort" in your library.

Bob Schor
Pascal Enthusiast

Other Threads