Keeping a sorted list vs sorting at the end?

Keeping a sorted list vs sorting at the end?

[jean-david hsu]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=UTF-8; format=flowed, Size: 503 bytes --]

Just wondering on the average if it is more efficient to take time to 
keep a list sorted as we insert or simply sort the list at the end?

JD Hsu

	
 p5.vert.ukl.yahoo.com uncompressed Sun Aug 20 03:27:01 GMT 2006 
	
		
___________________________________________________________________________ 
Découvrez un nouveau moyen de poser toutes vos questions quelque soit le sujet ! 
Yahoo! Questions/Réponses pour partager vos connaissances, vos opinions et vos expériences. 
http://fr.answers.yahoo.com 

Re: [Caml-list] Keeping a sorted list vs sorting at the end?

[Oliver Bandel]

On Sat, Aug 19, 2006 at 08:57:02PM -0700, jean-david hsu wrote:
> Just wondering on the average if it is more efficient to take time to 
> keep a list sorted as we insert or simply sort the list at the end?
> 
[...]

Sort list at the end.
If you want to sort at insertion time, then
trees are the better technique.

In OCaml there are the Set and the Map module, which
may be useful to you.

It depends on what you want to do, what kind of datastructure/module
is best suited.


Ciao,
   Oliver

Re: [Caml-list] Keeping a sorted list vs sorting at the end?

[David Powers]

[-- Attachment #1: Type: text/plain, Size: 2067 bytes --]

Rough analysis:

If the problem is general, keeping a list sorted is the equivalent of
inserting the members into a priority queue, which is O(n lg n) (for a
binary heap) going in and O(n) walking the tree if you have access to the
internal tree structure (vs calling a get-min function that rebalances the
tree over and over).  Non-general data (known bounds, etc) can be inseted
into a sorted data structure in less time.

Creating a list and then sorting it is O(n) for the list creation, then a
theoretical O(n lg n) for the sort (although possibly less (expected case)
in practice depending on the data and algorithm used), after which the items
can be read in O(n).  The problem with that is that, unless the data size is
known, the list must be constructed as a list and not an Array, which means
that the sort itself can be very slow (or adds another O(n) conversion step
from List to Array).

Final tally seems to very slightly favor the priority queue if it gives you
enough access to walk the sorted tree and you can create the tree from a
stream source of some sort.  If you already have the data in an Array, then
an in-place sort is likely to win.

-David


On 8/19/06, jean-david hsu <jhsu1@email.sjsu.edu> wrote:
>
> Just wondering on the average if it is more efficient to take time to
> keep a list sorted as we insert or simply sort the list at the end?
>
> JD Hsu
>
>
> p5.vert.ukl.yahoo.com uncompressed Sun Aug 20 03:27:01 GMT 2006
>
>
>
> ___________________________________________________________________________
> D�couvrez un nouveau moyen de poser toutes vos questions quelque soit le
> sujet !
> Yahoo! Questions/R�ponses pour partager vos connaissances, vos opinions et
> vos exp�riences.
> http://fr.answers.yahoo.com
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2711 bytes --]