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,
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.List
On 7/12/09, Heinrich Apfelmus apfel...@quantentunnel.de wrote:
Raynor Vliegendhart wrote:
On 7/9/09, Heinrich Apfelmus apfel...@quantentunnel.de wrote:
Of course, some part of algorithm has to be recursive, but this can be
outsourced to a general recursion scheme, like the hylomorphism
On Sun, Jul 12, 2009 at 07:01:11PM +0200, Raynor Vliegendhart wrote:
On 7/12/09, Heinrich Apfelmus apfel...@quantentunnel.de wrote:
Raynor Vliegendhart wrote:
On 7/9/09, Heinrich Apfelmus apfel...@quantentunnel.de wrote:
Of course, some part of algorithm has to be recursive, but this can
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
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
On Mon, Jul 6, 2009 at 12:26 PM, Petr Pudlakd...@pudlak.name 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 *
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 of my
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
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
On Mon, Jul 6, 2009 at 4:32 PM, Matthias
Görgensmatthias.goerg...@googlemail.com 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
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 (())
12 matches
Mail list logo
