> module Sorting where
INSERTION SORT
> insert :: Ord a => a -> [a] -> [a]
> insert a [] = [a]
> insert a (x:xs)
> | a<=x = a:x:xs
> | otherwise = x:(insert a xs)
> insSort :: Ord a => [a] -> [a]
> insSort [] = []
> insSort (a:as) = insert a (insSort as)
Complexity analysis.
Let U(n) be the time complexity of insert
as a function of the length n of the input list:
U(0) = c
U(n+1): if a<=x it is constant (just a cons)
otherwise it is U(n) plus a constant
<= U(n)+c
So U(n) <= c*n, that is U(n) = O(n)
Let T(n) be the time complexity of insSort
T(0) = c
T(n+1) = U(n)+T(n) = O(n)+T(n)
So T(n) = O(n^2)
BINARY SEARCH TREES
> data STree a = Leaf | Node a (STree a) (STree a)
> insTree :: Ord a => a -> STree a -> STree a
> insTree a Leaf = Node a Leaf Leaf
> insTree a (Node x t1 t2)
> | a<=x = Node x (insTree a t1) t2
> | otherwise = Node x t1 (insTree a t2)
> listTree :: Ord a => [a] -> STree a
> listTree [] = Leaf
> listTree (a:as) = insTree a (listTree as)
> treeList :: STree a -> [a]
> treeList Leaf = []
> treeList (Node x t1 t2) = (treeList t1) ++ x:(treeList t2)
> treeSort :: Ord a => [a] -> [a]
> treeSort = treeList . listTree
Complexity analysis
We mesure the size of a tree by the number of its nodes.
For a tree of the form (Node x t1 t2), we indicate
by n1 the size of t1, by n2 the size of t2, so n+1 = n1+n2+1
Let U(n) be the time complexity of insTree
U(0) = c
U(n+1) = U(n1+n2+1):
if a<=0 then U(n1)+c
otherwise U(n2)+c
<= U(n1+n2)+c = U(n)+c
So U(n) = O(n)
Notice that if we can guarantee that n1 and n2 are approximately equal
(the tree is balanced), then we would have U(n) = O(lg n).
Let V(n) be the time complexity of listTree
V(0) = c
V(n+1) = V(n) + U(n) = V(n) + O(n)
So V(n) = O(n^2)
Let W(n) be the time complexity of treeList
W(0) = c
W(n+1) = W(n1+n2+1) = W(n1) + W(n2) +c
So W(n) = O(n)
In conclusion the time complexity T(n) of treeSort is
T(n) = V(n) + W(n) = O(n^2)
A TYPE CLASS FOR DICTIONARIES
A type class specifies an abstract data types.
Instances of the type class are specific implementations of the specification.
> class Dictionary h where
> empty :: Ord a => h a
> isEmpty :: Ord a => h a -> Bool
> insDic :: Ord a => a -> h a -> h a
> search :: Ord a => a -> h a -> Bool
Here h is any type operator that maps a type a to a type h a.
The specification requires that, when a is in the Order class, then there are
four functions with the specified type.
Implementation of dictionaries using lists.
> instance Dictionary [] where
> empty = []
> isEmpty = null
> insDic = (:)
> search = elem
Implementation of dictionaries using binary search trees.
> instance Dictionary STree where
> empty = Leaf
> isEmpty Leaf = True
> isEmpty _ = False
> insDic = insTree
> search = searchTree
> searchTree :: Ord a => a -> STree a -> Bool
> searchTree a Leaf = False
> searchTree a (Node x t1 t2)
> | a==x = True
> | a<=x = searchTree a t1
> | otherwise = searchTree a t2
Can you improve the implementation by making sure to keep the tree balanced?