Created
June 2, 2025 22:51
-
-
Save emanoelbarreiros/f692f0e05d77f47343ad2fd0bd103a13 to your computer and use it in GitHub Desktop.
Counting sort implementation in Haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module CountingSort where | |
countingSort :: [Int] -> [Int] | |
countingSort [] = [] | |
countingSort ent = countingSortAux ent acum (n - 1) ret | |
where | |
n = length ent | |
contagem = [contar (==i) ent | i <- [0 .. (maximum ent)]] | |
acum = foldl (\x y -> if null x then [y] else x ++ [last x + y]) [] contagem | |
ret = replicate n 0 | |
countingSortAux ent acum j ret = if j < 0 | |
then ret | |
else countingSortAux ent (decr acum (ent !! j)) (j - 1) (upd ret ((acum !! (ent !! j)) - 1) (ent !! j)) | |
contar pred = length . filter pred | |
upd l p v = take p l ++ [v] ++ drop (p + 1) l | |
decr l p = take p l ++ [l !! p - 1] ++ drop (p + 1) l |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment