And just to remind people, the question is to find the indices and not
the numbers themselves. For example on input '3, [10,9,8,..., 3,2,1]'
the output must be '[9,8,7]'.
----- Original Message ----
From: Stefan O'Rear <stefanor@cox.net>
To: raghu vardhan <mrvr84@yahoo.co.in>
Sent: Wednesday, 11 April, 2007 11:17:15 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell
On Thu, Apr 12, 2007 at 09:30:22AM +0530, raghu vardhan wrote:
> Hmmm. That's not something I was looking for. I'm not sure the
> running time is good enough (think of k as being 2 - then you should
> not make more than 2n comparisons) - even with lazy evaluation,
> quick sort won't have a bound of O(k*n).
Muahahahaha!
Muahahahahahahahahahaha!
Muahaha!
Actually it DOES.
(this list courtesy of a ghci one-liner)
find the 3 minima of [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36]
============
take 3 (sort
[71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36])
vvvvvvvvvvvv
take 3 (sort (filter (<71) [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36]) ++ a bunch of stuff I won't track because it won't be evaluated)
vvvvvvvvvvvv (comparisons so far: 20)
take 3 (sort [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36])
take 3 (sort (filter (<17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]) ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))
vvvvvvvvvvvv (31)
take 3 (sort [14, 16, 18, 4] ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51,
36]))
take 3 (sort (filter (<14) [14, 16, 18, 4]) ++ sort (filter (==14) [14, 16, 18, 4]) ++ sort (filter (>14) [14, 16, 18, 4]) ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))
vvvvvvvvvvvv (39)
take 3 (sort [4] ++ sort [14] ++ sort (filter (>14) [14, 16, 18, 4]) ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))
take 3 (4 : 14 : sort (filter (>14) [14, 16, 18, 4]) ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18,
58, 65, 18, 4, 45, 51, 36]))
4 : 14 : take 1 (sort (filter (>14) [14, 16, 18, 4]) ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))
vvvvvvvvvvvv (43)
4 : 14 : take 1 (sort [16, 18] ++
filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))
vvvvvvvvvvvv (47)
[4, 14, 16]
47 close enough to O(n*k) for you? (remember this is quicksort we are
dealing with, O(n^2) worst case)
Stefan