> 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?