3 ms·
The haskell quicksort is also wrong : https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort https://s
by jcelerier 8y ago
The haskell quicksort is also wrong : https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort https://stackoverflow.com/questions/7717691/why-is-the-minim...
Here's the correct version taken from one of the SO answers :
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as M
qsort :: (V.Vector v a, Ord a) => v a -> v a
qsort = V.modify go where
go xs | M.length xs < 2 = return ()
| otherwise = do
p <- M.read xs (M.length xs `div` 2)
j <- M.unstablePartition (< p) xs
let (l, pr) = M.splitAt j xs
k <- M.unstablePartition (== p) pr
go l; go $ M.drop k pr
- pmarreck 8y agoWell according to the reasoning here, no purely functional quicksort will ever be "true quicksort" due to the apparent requirement that the sort be done in-place (mutably). Haskell may have well-thought-out mechanisms in place to do mutation "purely" (which are quite admirable IMHO) but this won't be the case with something like Elixir (Erlang). This code is also considerably more complex/less beautiful. I don't know what to call non-in-place Quicksort, but it deserves a name; in the meantime I will simply put it in quotes. It does seem possible to write an Elixir "quicksort" that does not consume gobs more space than "proper" quicksort, based on the comments there.
- waynecochran 8y agoThe following algorithm does not need any mutations: quicksort (list) if null(list) or else length(list) <= 1 return list else p = findpivot(list) (lo, hi) = split(p, list) return concat(quicksort(lo), quicksort(hi)) I still call it quicksort.