Anonymous user
Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 11:49, 3 November 2021
, 2 years ago→{{header|Haskell}}: added solution
m (→{{header|REXX}}: added wording to the REXX section header, allowd the starting number (of elements) to be specified on the command line.) |
(→{{header|Haskell}}: added solution) |
||
Line 1,228:
On random data (triangles) insertion and bubble sort show worse performance than quicksort.
<br clear=all>
=={{header|Haskell}}==
<lang haskell>import Data.Time.Clock
import Data.List
type Time = Integer
type Sorter a = [a] -> [a]
-- Simple timing function (in microseconds)
timed :: IO a -> IO (a, Time)
timed prog = do
t0 <- getCurrentTime
x <- prog
t1 <- x `seq` getCurrentTime
return (x, ceiling $ 1000000 * diffUTCTime t1 t0)
-- testing sorting algorithm on a given set
test :: [a] -> Sorter a -> IO [(Int, Time)]
test set srt = mapM (timed . run) ns
where
ns = take 15 $ iterate (\x -> (x * 5) `div` 3) 10
run n = pure $ length $ srt (take n set)
-- sample sets
constant = repeat 1
presorted = [1..]
random = (`mod` 100) <$> iterate step 42
where
step x = (x * a + c) `mod` m
(a, c, m) = (1103515245, 12345, 2^31-1)</lang>
As a result of testing we get the list of tuples: length of a list and time in microseconds:
<pre>λ> test ones sort
[(10,9),(16,7),(26,5),(43,5),(71,6),(118,8),(196,12),(326,18),(543,28),(905,41),(1508,68),(2513,108),(4188,191),(6980,303),(11633,484)]
λ> test rand sort
[(10,8),(16,7),(26,7),(43,9),(71,15),(118,24),(196,43),(326,82),(543,136),(905,270),(1508,482),(2513,1004),(4188,1926),(6980,4612),(11633,7286)]</pre>
Different sorting methods:
<lang haskell>-- Naive quick sort
qsort :: Ord a => Sorter a
qsort [] = []
qsort (h:t) = qsort (filter (< h) t) ++ [h] ++ qsort (filter (>= h) t)
-- Bubble sort
bsort :: Ord a => Sorter a
bsort s = case _bsort s of
t | t == s -> t
| otherwise -> bsort t
where _bsort (x:x2:xs) | x > x2 = x2:_bsort (x:xs)
| otherwise = x :_bsort (x2:xs)
_bsort s = s
-- Insertion sort
isort :: Ord a => Sorter a
isort = foldr insert []</lang>
Finally, charting routines and the task implementation:
<lang haskell>-- chart appears to be logarithmic scale on both axes
barChart :: Char -> [(Int, Time)] -> [String]
barChart ch lst = bar . scale <$> lst
where
scale (x,y) = (x, round $ (3*) $ log $ fromIntegral y)
bar (x,y) = show x ++ "\t" ++ replicate y ' ' ++ [ch]
over :: String -> String -> String
over s1 s2 = take n $ zipWith f (pad s1) (pad s2)
where
f ' ' c = c
f c ' ' = c
f y _ = y
pad = (++ repeat ' ')
n = length s1 `max` length s2
comparison :: Ord a => [Sorter a] -> [Char] -> [a] -> IO ()
comparison sortings chars set = do
results <- mapM (test set) sortings
let charts = zipWith barChart chars results
putStrLn $ replicate 50 '-'
mapM_ putStrLn $ foldl1 (zipWith over) charts
putStrLn $ replicate 50 '-'
let times = map (fromInteger . snd) <$> results
let ratios = mean . zipWith (flip (/)) (head times) <$> times
putStrLn "Comparing average time ratios:"
mapM_ putStrLn $ zipWith (\r s -> [s] ++ ": " ++ show r) ratios chars
where
mean lst = sum lst / genericLength lst
main = do
putStrLn "comparing on list of ones"
run ones
putStrLn "\ncomparing on presorted list"
run seqn
putStrLn "\ncomparing on shuffled list"
run rand
where
run = comparison [sort, isort, qsort, bsort] "siqb"</lang>
<pre>λ> main
comparing on list of ones
--------------------------------------------------
10 is b q
16 is b q
26 s b q
43 si b q
71 si b q
118 si b q
196 si b q
326 si b q
543 s i b q
905 s i b q
1508 s i b q
2513 s i b q
4188 s i b q
6980 s i b q
11633 s i b q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.9768226698141058
q: 4948.447011286744
b: 8.648711819912956
comparing on presorted list
--------------------------------------------------
10 isb q
16 s b q
26 s b q
43 i s b q
71 is b q
118 s b q
196 s b q
326 si b q
543 si b q
905 si b q
1508 si b q
2513 si b q
4188 s i b q
6980 s i b q
11633 s i b q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.2828547504398033
q: 2586.058542372048
b: 4.478306385307422
comparing on shuffled list
--------------------------------------------------
10 i qs
16 is q b
26 s q b
43 is q b
71 s q b
118 si q b
196 si q b
326 s i b
543 s qi b
905 s i b
1508 s q i b
2513 s q i b
4188 s q i b
6980 s q i b
11633 s q i b
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 33.0167854766955
q: 4.778965210071694
b: 920.9348663725772</pre>
We see that well known Haskell meme -- naive quicksort, is total mess on degenerate cases, and it does much better in general, still being significantly more slow then standard implementation. This tests were done in GHCi. Lazy Haskell program may be drastically rewritten and optimized during compilation. Let's see how it goes after compilation:
<pre>$ ghc -O2 CompareSort.hs
[1 of 1] Compiling Main ( CompareSort.hs, CompareSort.o )
Linking CompareSort ...
$ ./CompareSort
comparing on list of ones
--------------------------------------------------
10 i q s
16 s q
26 i s q
43 bs i q
71 ibs q
118 ibs q
196 ib s q
326 i bs q
543 bis q
905 i bs q
1508 ib s q
2513 ibs q
4188 ib s q
6980 si q
11633 si q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 0.9148588587463226
q: 751.3527462449417
b: 0.774109602468018
comparing on presorted list
--------------------------------------------------
10 i s
16 s q
26 s q
43 i s q
71 s q
118 sb q
196 is q
326 isb q
543 sb q
905 sb i q
1508 is q
2513 sb q
4188 is q
6980 ibs q
11633 s q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.114052564981571
q: 577.8734457264803
b: 1.1171025867573912
comparing on shuffled list
--------------------------------------------------
10 iqs
16 is
26 isb
43 sq b
71 si b
118 si b
196 s i b
326 sq i b
543 s i b
905 sq i b
1508 s q i b
2513 s q i b
4188 s q i b
6980 s q i b
11633 s q i b
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 29.346876854773274
q: 1.3750763918038253
b: 71.47503300525689</pre>
Even though quicksort still sucks on degenerate lists, it does really much better when compiled. Bubble sort had also improved it's rate, in contrast to insertion sort which didn't gain anything from compilation.
=={{header|J}}==
Line 1,464 ⟶ 1,716:
The data fit curves of the character cell graph were combined with GCD +. function. This explains "1"s or other strange values where these curves intersect. Finally the scatter plots were multiplied by infinity and added to the best fit curves. The points didn't show up well using the same values as the curves.
=={{header|Julia}}==
| |||