Anonymous user
Order by pair comparisons: Difference between revisions
→{{header|Haskell}}: added solution
Walterpachl (talk | contribs) m (→{{header|REXX}}: added rexx to lang tag) |
(→{{header|Haskell}}: added solution) |
||
Line 591:
[red orange yellow green blue indigo violet]
</pre>
=={{header|Haskell}}==
Injection of interaction with user is not straight-forward in pure functional language. In Haskell we use monads in order to abstract the computation flow and side effects. Fortunately the monadlist library [[https://hackage.haskell.org/package/monadlist]] contains monadic variants of most popular list operations so that it becomes easy to implement our favorite sorting algorithms.
<lang haskell>import Control.Monad
import Control.Monad.ListM (sortByM, insertByM, partitionM, minimumByM)
import Data.Bool (bool)
import Data.Monoid
import Data.List
--------------------------------------------------------------------------------
isortM, msortM, tsortM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a]
-- merge sort from the Control.Monad.ListM library
msortM = sortByM
-- insertion sort
isortM cmp = foldM (flip (insertByM cmp)) []
-- tree sort aka qsort (which is not)
tsortM cmp = go
where
go [] = pure []
go (h:t) = do (l, g) <- partitionM (fmap (LT /=) . cmp h) t
go l <+> pure [h] <+> go g
(<+>) = liftM2 (++)</lang>
Now we can sort lists with effects. For example, we may count number of comparisons, using writer monad:
<pre>*Main> let countComparisons cmp a b = (Sum 1, a `cmp` b)
*Main> msortM (countComparisons compare) [2,6,3,5,9,1,5]
(Sum {getSum = 15},[1,2,3,5,5,6,9])
*Main> isortM (countComparisons compare) [2,6,3,5,9,1,5]
(Sum {getSum = 15},[1,2,3,5,5,6,9])
*Main> tsortM (countComparisons compare) [2,6,3,5,9,1,5]
(Sum {getSum = 13},[1,2,3,5,5,6,9])</pre>
Or use a "database" as a reference for sorting, using reader monad
<pre>let fromList a b l = elemIndex a l `compare` elemIndex b l
*Main> msortM fromList [2,1,3,2,4,4,5,11,2,3,2,3] [1..]
[1,2,2,2,2,3,3,3,4,4,5,11]</pre>
Or even generate all possible permutations of a list making comparisons ambiguous:
<pre>*Main> isortM (\_ _ -> [LT, GT]) [1,2,3]
[[1,2,3],[1,3,2],[3,1,2],[2,1,3],[2,3,1],[3,2,1]]</pre>
We are ready to ask user to compare entries for us:
<lang haskell>ask a b = do
putStr $ show a ++ " ≤ " ++ show b ++ " ? [y/n] "
bool GT LT . ("y" ==) <$> getLine
colors = ["Violet", "Red", "Green", "Indigo", "Blue", "Yellow", "Orange"]</lang>
<pre>*Main> isortM ask colors
"Red" ≤ "Violet" ? [y/n] y
"Green" ≤ "Red" ? [y/n] n
"Green" ≤ "Violet" ? [y/n] y
"Indigo" ≤ "Red" ? [y/n] n
"Indigo" ≤ "Green" ? [y/n] n
"Indigo" ≤ "Violet" ? [y/n] y
"Blue" ≤ "Red" ? [y/n] n
"Blue" ≤ "Green" ? [y/n] n
"Blue" ≤ "Indigo" ? [y/n] y
"Yellow" ≤ "Red" ? [y/n] n
"Yellow" ≤ "Green" ? [y/n] y
"Orange" ≤ "Red" ? [y/n] n
"Orange" ≤ "Yellow" ? [y/n] y
["Red","Orange","Yellow","Green","Blue","Indigo","Violet"]
*Main> msortM ask colors
"Violet" ≤ "Red" ? [y/n] n
"Red" ≤ "Green" ? [y/n] y
"Green" ≤ "Indigo" ? [y/n] y
"Indigo" ≤ "Blue" ? [y/n] n
"Blue" ≤ "Yellow" ? [y/n] n
"Yellow" ≤ "Orange" ? [y/n] n
"Red" ≤ "Green" ? [y/n] y
"Violet" ≤ "Green" ? [y/n] n
"Violet" ≤ "Indigo" ? [y/n] n
"Red" ≤ "Orange" ? [y/n] y
"Green" ≤ "Orange" ? [y/n] n
"Green" ≤ "Yellow" ? [y/n] n
"Green" ≤ "Blue" ? [y/n] y
"Indigo" ≤ "Blue" ? [y/n] n
["Red","Orange","Yellow","Green","Blue","Indigo","Violet"]
*Main> tsortM ask colors
"Violet" ≤ "Red" ? [y/n] n
"Violet" ≤ "Green" ? [y/n] n
"Violet" ≤ "Indigo" ? [y/n] n
"Violet" ≤ "Blue" ? [y/n] n
"Violet" ≤ "Yellow" ? [y/n] n
"Violet" ≤ "Orange" ? [y/n] n
"Red" ≤ "Green" ? [y/n] y
"Red" ≤ "Indigo" ? [y/n] y
"Red" ≤ "Blue" ? [y/n] y
"Red" ≤ "Yellow" ? [y/n] y
"Red" ≤ "Orange" ? [y/n] y
"Green" ≤ "Indigo" ? [y/n] y
"Green" ≤ "Blue" ? [y/n] y
"Green" ≤ "Yellow" ? [y/n] n
"Green" ≤ "Orange" ? [y/n] n
"Yellow" ≤ "Orange" ? [y/n] n
"Indigo" ≤ "Blue" ? [y/n] n
["Red","Orange","Yellow","Green","Blue","Indigo","Violet"]</pre>
It seems that insertion sort with 13 comparisons is the best one, and tree sort which needed 17 questions is the worst. But efficiency of sorting depends on the order of given list. Simple statistics could be made to compare these three methods for all possible permutations of seven elements.
<lang haskell>test method = do
mapM_ showHist $ hist res
putStrLn $ "Median number of comparisons: " ++ show (median res)
putStrLn $ "Mean number of comparisons: " ++ show (mean res)
where
res = getSum . fst . method cmp <$> permutations [1..7]
cmp a b = (Sum 1, compare a b)
median lst = sort lst !! (length lst `div` 2)
mean lst = sum (fromIntegral <$> lst) / genericLength lst
hist lst = (\x -> (head x, length x)) <$> group (sort lst)
showHist (n, l) = putStrLn line
where
line = show n ++ "\t" ++ bar ++ " " ++ show perc ++ "%"
bar = replicate (max perc 1) '*'
perc = (100 * l) `div` product [1..7]</lang>
Comparing these three methods gives that for random inputs tree sort is the best choice.
<pre>*Main> test msortM
6 * 0%
7 * 0%
8 * 0%
9 * 0%
10 * 1%
11 *** 3%
12 ******* 7%
13 ******** 8%
14 **************** 16%
15 ************************ 24%
16 ************************ 24%
17 ************ 12%
Median number of comparisons: 15
Mean number of comparisons: 14.693055555555556
*Main> test isortM
6 * 0%
7 * 0%
8 * 0%
9 * 1%
10 *** 3%
11 ***** 5%
12 ******** 8%
13 ********** 10%
14 ************ 12%
15 ************* 13%
16 ************* 13%
17 *********** 11%
18 ******** 8%
19 ***** 5%
20 *** 3%
21 * 1%
Median number of comparisons: 15
Mean number of comparisons: 14.907142857142857
*Main> test tsortM
10 * 1%
11 ******************** 20%
12 ******************** 20%
13 ***************** 17%
14 ******** 8%
15 ************* 13%
16 ***** 5%
17 ****** 6%
18 ** 2%
19 * 1%
20 * 0%
21 * 1%
Median number of comparisons: 13
Mean number of comparisons: 13.485714285714286</pre>
=={{header|Java}}==
| |||