TEAM-ADA Archives

Team Ada: Ada Programming Language Advocacy

TEAM-ADA@LISTSERV.ACM.ORG

Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Condense Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< 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]>
Subject:
MIME-Version:
1.0
Content-Transfer-Encoding:
7bit
In-Reply-To:
Content-Type:
text/plain; charset="US-ASCII"
From:
Steven Deller <[log in to unmask]>
Parts/Attachments:
text/plain (49 lines)
Jesse,
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 =
4096
sorting "operations", versus 65536 sorting "operations" doing the whole
list.

Regards,
Steve

P.S. The indirectsort approach has one additional benefit, namely you can
create
a "stable" sort from non-stable sort with just a minor change to the
Rearrange_List
code.  You keep the Li list intact, keep the "sorted" information in an
associated
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.

ATOM RSS1 RSS2