\section{Introduction}
This module defines, and tests various sort functions written is Haskell.
I descided to do this rather trivial exercise, to accustom myself with
the prototype Glasgow Haskell compiler, and Glasgows literate programming
system.
Use of this module is obtained by importing the module, and {\em one} of the
sort functions which will be renamed to {\tt sort} -
i.e ``{\tt import Sort(lazySort) renaming sort}'' imports {\tt lazySort},
which can be referenced in the current scope as {\tt sort}.
\begin{code}
module Sort(insertSort,mergeSort,quickSort,lazySort) where
-- import PrelNum( Num(fromInt) )
-- import GlaExts( Num(fromInt) ) -- Shouldn't really use this in a benchmark,
-- but don't want change wrt old baselines
fromInt = fromInteger . toInteger
\end{code}
%%%%%%%%%%%%%%%%%%%%%%I n s e r t i o n S o r t%%%%%%%%%%%%%%%%%%%%%%
\section{Insertion Sort}
The following piece of code is taken from the Gofer manual.
%
\begin{code}
insertSort::(Ord a) => [a] -> [a]
insertSort xs = foldr insertion [] xs
insertion :: (Ord a) => a -> [a] -> [a]
insertion x [] = [x]
insertion x (y:ys)
| x <= y = x:y:ys
| otherwise = y:insertion x ys
\end{code}
%%%%%%%%%%%%%%%%%%%%%%%%%%M e r g e S o r t%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Merge Sort}
The following code is taken from Keiths ''Functional Programming 2''
lecture notes.
%
\begin{code}
mergeSort :: (Ord a) => [a] -> [a]
mergeSort xs
= if (n <=1 ) then xs
else
(mergeList
( mergeSort (take (n `div` 2) xs))
( mergeSort (drop (n `div` 2) xs)))
where
n = length xs
mergeList :: (Ord a) => [a] -> [a] -> [a]
mergeList [] ys = ys
mergeList xs [] = xs
mergeList (x:xs) (y:ys)
| x <= y = x:mergeList xs (y:ys)
| otherwise = y:mergeList (x:xs) ys
\end{code}
%%%%%%%%%%%%%%%%%%%%%%%%%%Q u i c k S o r t%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A not so ``Quick Sort''}
Standard definition of quicksort\cite{turner} using list comprehensions.
\begin{code}
quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = (quickSort [y | y<-xs, y<x]) ++ [x] ++
(quickSort [y | y<-xs, y>=x])
\end{code}
%%%%%%%%%%%%%%%%%%%%%%L e n n a r t s S o r t%%%%%%%%%%%%%%%%%%%%%%%
\section{Lennart Augustsson's ``Quick Sort''}
This module implements a sort function using a variation on
quicksort. It is stable, uses no concatenation and compares
only with {\tt <=}.
%
\begin{rawlatex}
\begin{itemize}
\item {\tt sortLe} sorts with a given predicate
\item {\tt lazySort} uses the {\tt <=} method
\end{itemize}
\end{rawlatex}
%
\begin{code}
lazySortLe :: (a -> a -> Bool) -> [a] -> [a]
lazySortLe le l = lazyQsort le l []
lazySort :: (Ord a) => [a] -> [a]
lazySort l = lazyQsort (<=) l []
-- lazyQsort is stable and does not concatenate.
lazyQsort :: (a -> a -> Bool) -> [a] -> [a] -> [a]
lazyQsort le [] r = r
lazyQsort le [x] r = x:r
lazyQsort le (x:xs) r = qpart le x xs [] [] r
-- rlazyQsort is as lazyQsort but anti-stable,
-- i.e. reverses equal elements.
rlazyQsort :: (a -> a -> Bool) -> [a] -> [a] -> [a]
rlazyQsort le [] r = r
rlazyQsort le [x] r = x:r
rlazyQsort le (x:xs) r = rqpart le x xs [] [] r
-- qpart partitions and sorts the sublists
-- rlt and rge are in reverse order and must be sorted with an
-- anti-stable sorting
qpart :: (a -> a -> Bool) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
qpart le x [] rlt rge r =
rlazyQsort le rlt (x:rlazyQsort le rge r)
qpart le x (y:ys) rlt rge r =
if le x y then
qpart le x ys rlt (y:rge) r
else
qpart le x ys (y:rlt) rge r
rqpart :: (a -> a -> Bool) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
rqpart le x [] rle rgt r =
lazyQsort le rle (x:lazyQsort le rgt r)
rqpart le x (y:ys) rle rgt r =
if le y x then
rqpart le x ys (y:rle) rgt r
else
rqpart le x ys rle (y:rgt) r
\end{code}
%%%%%%%%%%%%%%%%%%%%%%R a n d o m N u m b e r s%%%%%%%%%%%%%%%%%%%%%%%
\section{Random Number Generator}
This module implements a (good) random number generator.
The June 1988 (v31 \#6) issue of the Communications of the ACM has an
article by Pierre L'Ecuyer called, "Efficient and Portable Combined
Random Number Generators". Here is the Portable Combined Generator of
L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18.
Transliterator: Lennart Augustsson
Use seeds s1 in 1..2147483562 and s2 in 1..2147483398 to generate
an infinite list of random Ints.
\subsection{Random Integers}
\begin{code}
randomInts :: Int -> Int -> [Int]
randomInts s1 s2 =
if 1 <= s1 && s1 <= 2147483562 then
if 1 <= s2 && s2 <= 2147483398 then
rands s1 s2
else
error "randomInts: Bad second seed."
else
error "randomInts: Bad first seed."
rands :: Int -> Int -> [Int]
rands s1 s2
= if z < 1 then z + 2147483562 : rands s1'' s2''
else
z : rands s1'' s2''
where
k = s1 `div` 53668
s1' = 40014 * (s1 - k * 53668) - k * 12211
s1'' = if s1' < 0 then s1' + 2147483563 else s1'
k' = s2 `div` 52774
s2' = 40692 * (s2 - k' * 52774) - k' * 3791
s2'' = if s2' < 0 then s2' + 2147483399 else s2'
z = s1'' - s2''
\end{code}
\subsection{Random Doubles}
Same values for s1 and s2 as above, generates an infinite
list of Doubles uniformly distibuted in (0,1).
\begin{code}
randomDoubles :: Int -> Int -> [Double]
randomDoubles s1 s2 = map (\x -> (fromIntegral x * 4.6566130638969828e-10))
(randomInts s1 s2)
\end{code}
\section{Test Data}
\begin{code}
test1,test2,test3,test4,test5,test6,test7::[Int]
test1 = [1..10]
test2 = [10,9..1]
test3 = [1..500]
test4 = [500,499..1]
test5 = take 10 (randomInts 123213 342234)
test6 = take 100 (randomInts 123213 342234)
test7 = take 1000 (randomInts 123213 342234)
\end{code}
\section{Results}
\begin{rawlatex}
\begin{tabular}{||c||r|r||r|r||r|r||r|r||}
\hline
& \multicolumn{2}{c||}{insertSort} &
\multicolumn{2}{c||}{mergeSort} &
\multicolumn{2}{c||}{quickSort} &
\multicolumn{2}{c||}{lazySort} \\
\cline{2-9}
& \multicolumn{1}{c|}{red} &
\multicolumn{1}{c||}{cell} &
\multicolumn{1}{c|}{red} &
\multicolumn{1}{c||}{cell} &
\multicolumn{1}{c|}{red} &
\multicolumn{1}{c||}{cell} &
\multicolumn{1}{c|}{red} &
\multicolumn{1}{c||}{cell}\\
\hline\hline
test1 & 112 & 225 &
360 & 636 &
362 & 640 &
140 & 501 \\
\hline
test2 & 184 & 368 &
367 & 662 &
542 & 910 &
140 & 501 \\
\hline
test3 & 5009 & 11406 &
35309 & 63196 &
753002 & 1135146 &
252000 & 883637 \\
\hline
test4 & 253517 & 507919 &
35422 & 63590 &
1252003 & 1883646 &
252000 & 883637 \\
\hline
test5 & 363 & 963 &
373 & 768 &
324 & 668 &
367 & 1073 \\
\hline
test6 & 8366 & 19254 &
6077 & 12273 &
6002 & 10791 &
4314 & 13514 \\
\hline
test7 & 519754 & 1065013 &
84228 & 170230 &
95620 & 161432 &
25416 & 98789 \\
\hline
\end{tabular}
\end{rawlatex}
|
