2010/10/8 "Jérôme M. Berger" <jeber...@free.fr> > Steven Schveighoffer wrote: > > On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke <rain...@eldwood.com> > > wrote: > > > >> On 10/7/2010 13:57, Andrei Alexandrescu wrote: > >>> On 10/7/10 14:40 CDT, bearophile wrote: > >>>> Another solution is just to accept O(n) as the worst complexity for > >>>> the "in" operator. I don't understand what's the problem in this. > >>> > >>> That means we'd have to define another operation, i.e. "quickIn" that > >>> has O(log n) bound. > >> > >> Why? > >> > >> I can't say I've ever cared about the big-O complexity of an operation. > > > > Then you don't understand how important it is. > > If big O complexity is so important, then why does everyone use > quicksort (which is O(n**2)) and not heap sort or merge sort (which > are O(n*log(n)))? > > Jerome > -- > mailto:jeber...@free.fr > http://jeberger.free.fr > Jabber: jeber...@jabber.fr > >
Because on average quicksort is faster than heap sort, and uses much less space than merge sort. Also, trivial guards can be put in place to avoid running quicksort in a worst case (pre-sorted data) scenario.
