English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Keeping a sorted list vs sorting at the end?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-08-20 (16:09)
From: David Powers <david@g...>
Subject: Re: [Caml-list] Keeping a sorted list vs sorting at the end?
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.


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