30 Mar
2014
30 Mar
'14
10:06 a.m.
Am 03/24/2014 12:34 AM, schrieb John Lato:
I would keep in mind that, given the constraints
- you want to group together all equal elements from the entire list - the only operation you can perform on elements is comparison for equality
your function will have quadratic complexity (at least I can't see any way around it).
Wouldn't a modified quicksort give n*log(n) complexity. Something like: groupEq [] = [] groupEq (x:xs) = (groupEq a) ++ [x] ++ (groupEq b) where a = filter (==x) xs b = filter (/= x) xs This is indeed much slower than the built-in sort, but it slower too whern I replace "==" with ">", resulting in a texbook quicksort.