Order by pair comparisons: Difference between revisions
Content added Content deleted
Walterpachl (talk | contribs) m (→{{header|REXX}}: added rexx to lang tag) |
(→{{header|Haskell}}: added solution) |
||
Line 591: | Line 591: | ||
[red orange yellow green blue indigo violet] |
[red orange yellow green blue indigo violet] |
||
</pre> |
</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}}== |
=={{header|Java}}== |