This is the mail archive of the
gsl-discuss@sources.redhat.com
mailing list for the GSL project.
Re: a question about gsl_sort_***
- From: Brian Gough <bjg at network-theory dot co dot uk>
- To: Arin Chaudhuri <achaudh at unity dot ncsu dot edu>
- Cc: gsl-discuss at sources dot redhat dot com
- Date: Sat, 27 Sep 2003 10:15:47 +0100
- Subject: Re: a question about gsl_sort_***
- References: <Pine.GSO.4.58.0309270211060.13107@uni03du.unity.ncsu.edu>
Arin Chaudhuri writes:
> Dr. Gough,
> I don't know much about design issues but I was wondering about
> the reason behind the choice of algorithm gsl_sort_smallest. I was
> wondering about this simple alternative:
> We build a heap then we simply pull out the k largest elements. The most
> efficient method of building a heap is O(N) pulling out k
> elements from the heap require a further klog(N) steps, but of course
> for this we will have to make a copy of the original array. Unless the
> cost of duplicating a large array makes up for the decrease in complexity
> from kN to cN+klog(N) we should be fine, or am I missing something?
> regards,
> Arin
I wanted an algorithm that did not use any extra memory and preserved
the original array. It is possible to use a heap for the k elements,
which increases the efficiency for large k, but I implemented the
easier option of direct insertion since large k is not often used in
practice. See Knuth vol 3 for all relevant details.
--
Brian