Sorting algorithms/Counting sort: Difference between revisions
Content added Content deleted
(added ocaml version for arrays; maybe someone else can add one for lists) |
|||
| Line 224: | Line 224: | ||
countingSort :: (Enum n, Ix n) => [n] -> n -> n -> [n] |
countingSort :: (Enum n, Ix n) => [n] -> n -> n -> [n] |
||
countingSort l lo hi = |
countingSort l lo hi = concatMap (uncurry $ flip replicate) count |
||
where count = runST $ do |
where count = runST $ do |
||
a <- myNewArray (lo, hi) 0 |
a <- myNewArray (lo, hi) 0 |
||
let increment i = readArray a i >>= writeArray a i . (+1) |
let increment i = readArray a i >>= writeArray a i . (+1) |
||
mapM_ increment l |
mapM_ increment l |
||
getAssocs a |
|||
myNewArray :: (Ix n) => (n,n) -> Int -> ST s (STArray s n Int) |
myNewArray :: (Ix n) => (n,n) -> Int -> ST s (STArray s n Int) |
||
myNewArray = newArray</lang> |
myNewArray = newArray</lang> |
||