TEAM-ADA Archives

Team Ada: Ada Programming Language Advocacy


Options: Use Classic View

Use Monospaced Font
Show Text Part by Default
Condense Mail Headers

Topic: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Sender: "Team Ada: Ada Advocacy Issues (83 & 95)" <[log in to unmask]>
Date: Mon, 18 Dec 2000 16:58:39 -0500
Reply-To: Steven Deller <[log in to unmask]>
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
In-Reply-To: <[log in to unmask]>
Content-Type: text/plain; charset="US-ASCII"
From: Steven Deller <[log in to unmask]>
Parts/Attachments: text/plain (49 lines)
One last thing I missed in your original questions:

> ...
> One of the thing I wonder about, is should I have my program
> sort the whole array in one step, or have my code step thru each Letter
> Prefix.  If I have it go thru and just do a Letter worth at a
> time, it will
> almost certainly always be under 20 things to sort per letter.  Because of
> the small number of objects I would be sorting in this case, I'm also
> considering shell sort, or insertion sort.

Without a doubt you should sort the array "one letter at a time".

The best algorithms are O(NlnN).  Consider the following:
  N    NlnN  N**2
  2    2     4
  4    8     16
  8    24    64
  16   64    256
  256  4096  65536
  512  4608  262144
  1024 10240  1048576

So let's say you have 256 total items, with 16 letters of 16 items each.

Using an O(NlnN) algorithm, if you sort each one individually, you get 16*64
= 1024
sorting "operations", versus 4096 sorting "operations" doing the whole list.

Using an O(N**2) algorithm, sort each one individually, you get 16*256 =
sorting "operations", versus 65536 sorting "operations" doing the whole


P.S. The indirectsort approach has one additional benefit, namely you can
a "stable" sort from non-stable sort with just a minor change to the
code.  You keep the Li list intact, keep the "sorted" information in an
bit-array, and then make a final pass to find and rearrange *equal* members
to their
original order. Let me know if you want the details.