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