Most efficient sort text file routine, sort algorithms

Most efficient sort text file routine, sort algorithms

Post by Matth » Fri, 16 May 1997 04:00:00



I have a text file. Each line begins with a date like "19970515".
There might be up to a few hundred dates in this text file, possibly
in random order, but I cannot be sure
someone might not put thousands of lines in there.

I am avoiding a database with an index, because
that way users cannot edit the text file with Notepad.exe or other
text editor.

File example:

19970514 This is a record
19970521 This is more info
19961212 This is some data
19980202 This is another record
19950608 This is yet more info

I am looking for a clever way to sort this file in the most efficient
manner. Each line is less than 255 characters.

So I am thinking:

 TStringList.loadFromFile;
 TStringList.sort;
 TStringList.saveToFile;

Using Delphi 16-bit, I wonder, what are the limits to the number of
strings?  If the limit is 64K, and 200 bytes per
line, then 5 records per K, 60*5 +4*5 = 300+20= 320 records
max. That would not be enough.

I seem to remember some old-fashioned sort algorithm. Two files would
run against each other with some sort of buffer where records are
compared, but don't recall how this is done without scanning and
re-reading the entire
file countless numbers of times.

Email me. I reply to every email.
Matthew

 
 
 

Most efficient sort text file routine, sort algorithms

Post by Sundial Servic » Sat, 17 May 1997 04:00:00



>I have a text file. Each line begins with a date like "19970515".
>There might be up to a few hundred dates in this text file, possibly
>in random order, but I cannot be sure
>someone might not put thousands of lines in there.
>I am avoiding a database with an index, because
>that way users cannot edit the text file with Notepad.exe or other
>text editor.
>File example:
>19970514 This is a record
>19970521 This is more info
>19961212 This is some data
>19980202 This is another record
>19950608 This is yet more info
>I am looking for a clever way to sort this file in the most efficient
>manner. Each line is less than 255 characters.
>So I am thinking:
> TStringList.loadFromFile;
> TStringList.sort;
> TStringList.saveToFile;
>Using Delphi 16-bit, I wonder, what are the limits to the number of
>strings?  If the limit is 64K, and 200 bytes per
>line, then 5 records per K, 60*5 +4*5 = 300+20= 320 records
>max. That would not be enough.
>I seem to remember some old-fashioned sort algorithm. Two files would
>run against each other with some sort of buffer where records are
>compared, but don't recall how this is done without scanning and
>re-reading the entire
>file countless numbers of times.
>Email me. I reply to every email.
>Matthew

Umm... TurboPower Software sells a great sort engine as part of its SysTools
package.  Generally speaking the best way to get a large-scale sort done is to
buy a package to do it.  Seriously.  I mean that very seriously!

 
 
 

Most efficient sort text file routine, sort algorithms

Post by Robert Kapla » Sun, 18 May 1997 04:00:00




> >I have a text file. Each line begins with a date like "19970515".
> >There might be up to a few hundred dates in this text file, possibly
> >in random order, but I cannot be sure
> >someone might not put thousands of lines in there.

> >I am avoiding a database with an index, because
> >that way users cannot edit the text file with Notepad.exe or other
> >text editor.

> >File example:

> >19970514 This is a record
> >19970521 This is more info
> >19961212 This is some data
> >19980202 This is another record
> >19950608 This is yet more info

> >I am looking for a clever way to sort this file in the most efficient
> >manner. Each line is less than 255 characters.

> >So I am thinking:

> > TStringList.loadFromFile;
> > TStringList.sort;
> > TStringList.saveToFile;

> >Using Delphi 16-bit, I wonder, what are the limits to the number of
> >strings?  If the limit is 64K, and 200 bytes per
> >line, then 5 records per K, 60*5 +4*5 = 300+20= 320 records
> >max. That would not be enough.

> >I seem to remember some old-fashioned sort algorithm. Two files would
> >run against each other with some sort of buffer where records are
> >compared, but don't recall how this is done without scanning and
> >re-reading the entire
> >file countless numbers of times.

> >Email me. I reply to every email.
> >Matthew

> Umm... TurboPower Software sells a great sort engine as part of its SysTools
> package.  Generally speaking the best way to get a large-scale sort done is to
> buy a package to do it.  Seriously.  I mean that very seriously!

Turbo Power used to give away their Pascal sort (MSortP), works great.
Yo should be able to port it to Delphi.
--

Robert

Return address changed to deter malevolent spammers.

 
 
 

1. Big oh statistics for maximum moves of new patented sorting algorithm better than heap sort


The maximum number of moves is N * ( ( b - 1)/2).

The maximum number of moves with rewrite of the sorted list is:

        N * ( ( b - 1)/2) + ( INT( N / b) * b)

where b is the number of blanks used.

In contrast to a heap sort (the best performer for number of moves at n lg n), for b =
11, the above algorithm has over 40% fewer moves.

2. RAIMA database

3. XML manipulation in PL/SQL (non 8i/9i)

4. InterBase Security

5. Delphi: BDE-Aliase von Programmen aus anlegen ???

6. Big-oh statistics for average compares and moves of new patented sorting algorithm are 2- to 8-times less than for quick sort and radix sort

7. Most efficient DBproc when sorting?

8. Sorting when importing from a text file