Subj : Re: Sorting
To   : borland.public.cpp.borlandcpp
From : "Dwayne" <myfrienddr@yahoo.com>
Date : Sun Dec 21 2003 11:04 am

Dwayne>     Well, a cheap simple way to do so, would be to hash the file.
Build a
> tree, and as you
> read through the file once, your tree is built, and presto...instant
> sorting.  I built a Btree that
> works directly off your hard drive... thus you have unlimited amount of
> memory (except your hard
> drive space).   It works wonderfully and is extremely fast.  At times, I
> will sort 2 to 8 million things at once.

Georges>>That sound wonderful but could you be alitle more explanatory to a
relative
beginner!  For example, what's a BTree ?<<

      To give you a example.

      You start off with your first item.  (it is the base starting point).
 Take your second item and compare it to the first.  If it is less or equal,
but it below and to the left.  If it is greater, put it below and to the
right.  (these are called nodes).  You do this with each time, and you will
end up with a upside down tree.

       sorting the numbers  5,3,7,1,9,4
                     5
                 /          \
                3          7
            /      \            \
          1        4            9


    Now, if you have the number 7 you only have to look down 2 nodes to find
it.  #1 is 5, and the #2 is the number.

    With extremely large files, you can find about anything you want rather
quickly.   Under the *BEST* possible conditions you will be able to find
anything you want in 2^n times.  If you have 1 million records, you only
have to look at 20 records to know whether that record exists or not.   Thus
it is extremely fast.
You only have to look at 30 records to find 1 record in over 1 billion.  30
records is a blink of a eye at the slowest <g>.

       When you build this tree, you write a program to work through the
tree and find your records that you need.  I built my program to run on a
disk, because sometimes I work with extremely large number of records.
Anyhwhere from 2 to 8 million different pieces.  I have gone as high as 15
million different pieces.  What I like about my tree on a file, it is
unlimited, and it is totally on disk.  You do not have to worry about
running out of memory in your RAM.  I think my libraries for my routines are
only about 50K total.  That means RAM resources are extremely low.

      A tree search is very similar to the Binary search.  The only
difference is, a Binary search *must* have the records in sorted order to
work, and you start in the "middle of the file/records".

       This is a rather "watered down" version, but it may give you somewhat
of a idea to work with.

                                    Dwayne

.