A three-way quicksort can use a common partition helper so that the tree factorisation below makes the same key comparisons. The Every non-pivot entry appears in exactly one partition, and the equal bucket contains the original pivot exactly once. The recursive sublists have length at most one less than the current finite input, so recursion terminates. Induction gives sorted recursive results with the original multiplicities; placing the equal bucket between them gives a sorted permutation of the input. There is no recursive call on the equal bucket, which avoids needless descent on repeated keys.
compare operation is assumed to be a terminating lawful total ordering on the supplied keys.partition3 :: Ord a => a -> [a] -> ([a],[a],[a])
partition3 pivot = foldr step ([],[],[])
where
step x rest =
let (lo,eq,hi) = rest
in case compare x pivot of
LT -> (x:lo,eq,hi)
EQ -> (lo,x:eq,hi)
GT -> (lo,eq,x:hi)
sort :: Ord a => [a] -> [a]
sort [] = []
sort (pivot:xs) =
let (lo,eq,hi) = partition3 pivot xs
in sort lo ++ (pivot:eq) ++ sort hiThe ordering operations used to decide the partitions require an
Ord a constraint. A function with parametric polymorphism and type [a] -> [a] cannot inspect arbitrary element values to decide which one is smaller; for example, functions themselves need not admit the comparison operations required by this sorting algorithm. A Haskell Ord class instance supplies the comparison method, with its ordering laws a separate semantic assumption.[ref]Haskell 2010 Language Report. Chapter 9, the Ord class and compare method
Store the equal bucket at each internal node:The representation invariant for a tree produced by
data Tree a = Empty | Node (Tree a) [a] (Tree a)
toTree :: Ord a => [a] -> Tree a
toTree [] = Empty
toTree (pivot:xs) =
let (lo,eq,hi) = partition3 pivot xs
in Node (toTree lo) (pivot:eq) (toTree hi)
fromTree :: Tree a -> [a]
fromTree Empty = []
fromTree (Node left equal right) =
fromTree left ++ equal ++ fromTree righttoTree is that its bucket is nonempty and contains equal keys, every left-subtree key is smaller, and every right-subtree key is larger. Its multiplicities are preserved. Substituting the two equations for toTree into fromTree gives exactly the two defining equations for sort; induction proves sort = fromTree . toTree on finite inputs.Both versions call the same partition helper on the same pivot and sublists. The flattening stage makes no key comparisons. Thus fully producing the answer makes the same comparison decisions as the direct algorithm; no additional comparison against stored tree keys is introduced.
toTree needs Ord a; fromTree does not. Construction compares each key against a pivot. Flattening merely traverses and concatenates the buckets, so its more general type is Tree a -> [a]. A manually constructed tree need not satisfy the search-tree invariant; fromTree still flattens it, although its output need not be sorted.A tree fold replaces each constructor by its interpretation:Induction on the finite tree shows equality with
foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
combine (foldTree combine zero left)
equal
(foldTree combine zero right)
fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []fromTree: the empty tree produces the empty output, and the combining function concatenates the two correctly flattened children around the node's bucket. The result type is independent of the key type; other choices can compute a size or another summary using the same structural recursion.An unfold expands a seed into either no node or a bucket and two new seeds:The seed is the remaining list. Expanding a nonempty seed partitions it exactly as
unfoldTree :: (s -> Maybe (s,[a],s)) -> s -> Tree a
unfoldTree split seed =
case split seed of
Nothing -> Empty
Just (left,equal,right) ->
Node (unfoldTree split left) equal (unfoldTree split right)
toTreeUnfold :: Ord a => [a] -> Tree a
toTreeUnfold = unfoldTree split
where
split [] = Nothing
split (pivot:xs) =
let (lo,eq,hi) = partition3 pivot xs
in Just (lo,pivot:eq,hi)toTree does, and both child seeds are shorter. Induction establishes toTreeUnfold = toTree and algorithm termination on finite inputs. The unfold separates the local decomposition rule from the recursive construction of the tree. Articles by others on the same topic
There are currently no matching articles.