[Haskell-beginners] sorting almost sorted list
gale at sefer.org
Tue Sep 27 11:32:35 CEST 2011
> Can you guarantee for some value of m that for each note N,
> only the first m notes following N might end earlier than N?
> If so, then the following simple algorithm is linear
> and runs in constant space. You could then use:
> sortAlmostBy m (comparing endTime)
> ...You might be able to do a little better than this.
After running some tests, it seems empirically that
you can use m `div` 2 instead of m for lists of even
length, which gives you a nice speedup for larger
values of m. For lists of prime length, the best
you can do seems to be m-1. It's more complicated
for lists of non-prime odd length.
I can't immediately see why any of that is true.
Daniel to the rescue perhaps?
test n k = fmap (all isSorted . map (sortAlmostBy n compare)) $ rands k
isSorted xs = and . zipWith (<=) xs $ drop 1 xs
rands d = fmap (take 100 . map (concat . zipWith (map . (+)) [0,d ..]
. chunksOf d) . chunksOf 1000 . randomRs (0, d-1)) newStdGen
More information about the Beginners