Hi all,
I apologize that I didn't react to your posts, I was on a vacation. (BTW, if
you ever come to Slovakia, I strongly recommend visiting Mala (Lesser) Fatra
mountains. IMHO it's more beautiful than more-known Tatra mountains.)
Thanks for your interest and many intriguing ideas. Especially, I
On Sun, Jul 12, 2009 at 07:01:11PM +0200, Raynor Vliegendhart wrote:
> On 7/12/09, Heinrich Apfelmus wrote:
> > Raynor Vliegendhart wrote:
> > > On 7/9/09, Heinrich Apfelmus wrote:
> > >> Of course, some part of algorithm has to be recursive, but this can be
> > >> outsourced to a general recursi
On 7/12/09, Heinrich Apfelmus wrote:
> Raynor Vliegendhart wrote:
> > On 7/9/09, Heinrich Apfelmus wrote:
> >> Of course, some part of algorithm has to be recursive, but this can be
> >> outsourced to a general recursion scheme, like the hylomorphism
> >>
> >>hylo :: Functor f => (a -> f a) -
Petr Pudlak wrote:
> Would it be possible to create a lazy selection/sorting
> algorithm so that getting any element of the sorted list/array by its index
> would require just O(n) time, and getting all the elements would still be in
> O(n * log n)?
The (merge) sorting algorithm provided by Data.L
The "sorted array of bags of unsorted input" is a nice idea. However,
you have to use the data structure in a single-threaded [1] fashion to
obtain the claimed bounds.
Here's a pure solution that uses amortization and laziness.
> import qualified Data.Sequence as S
> import Data.Sequence ((><))
On Mon, Jul 6, 2009 at 4:32 PM, Matthias
Görgens wrote:
>> It seems to me, that you just need a selection algorithm which works in
>> O(n * k) time for k arbitrary elements. If you combine O(n*k) selection
>> algorithm with any O(n * lg n) sort, you furfil your time constrain.
>
> I guess, we also
> It seems to me, that you just need a selection algorithm which works in
> O(n * k) time for k arbitrary elements. If you combine O(n*k) selection
> algorithm with any O(n * lg n) sort, you furfil your time constrain.
I guess, we also want the list to be sorted in O(1) after having
selected every
Hi Petr,
Maybe this will give inspiration
http://en.wikipedia.org/wiki/Selection_algorithm
It seems to me, that you just need a selection algorithm which works in
O(n * k) time for k arbitrary elements. If you combine O(n*k) selection
algorithm with any O(n * lg n) sort, you furfil your time cons
> If someone can translate my algorithm into a non-side-effecting one,
> I'd appreciate it, but I think that like disjoint set/union, this is
> probably inherently side-effecting. Yes, yes, we could use functional
> arrays, but short of that I don't see a way to avoid side effects to
> take care o
On Mon, Jul 6, 2009 at 12:26 PM, Petr Pudlak wrote:
> More precisely: The result of sorting an n-element list or array should be a
> structure that allows to ask i-th element of the result (for example, a lazy
> array). Asking k arbitrary elements should take no more than
> O(min(n * log n, k * n)
Interesting problem. I have been toying with the same problem for some time.
To solve the problem in theory, I'd concentrate on getting the number
of comparisons into the required O(n) resp. O(n log n) ranges.
Afterwards we can think about building the infrastructure to keep the
number of all ope
Hi all,
about a month ago, we were discussing sorting in Haskell with a friend. We
realized a nice property of lazy merge-sort (which is AFAIK the implementation
of Data.List.sort): Getting the first element of the sorted list actually
requires O(n) time, not O(n * log n) as in imperative language
12 matches
Mail list logo