Keeping a sorted list vs sorting at the end?

jeandavid hsu
 Oliver Bandel
 David Powers
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060820 (16:09) 
From:  David Powers <david@g...> 
Subject:  Re: [Camllist] 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 getmin function that rebalances the tree over and over). Nongeneral 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 inplace sort is likely to win. David On 8/19/06, jeandavid 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 > > _______________________________________________ > Camllist mailing list. Subscription management: > http://yquem.inria.fr/cgibin/mailman/listinfo/camllist > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/camlbugs >