Module Sort

sort :: Ord a => [a] -> [a]   

The default sorting operation, mergeSort, with standard ordering <=.

Postcondition:

ys = sort xs satisfies (length xs == length ys) && sorted ys (sort'post)

Specification:

(sort xs) is equivalent to permSort xs (sort'spec)

sortBy :: (a -> a -> Bool) -> [a] -> [a]   

The default sorting operation: mergeSort

sorted :: Ord a => [a] -> Bool   

sorted xs is satisfied if the elements xs are in ascending order.

sortedBy :: (a -> a -> Bool) -> [a] -> Bool   

sortedBy leq xs is satisfied if all adjacent elements of the list xs satisfy the ordering predicate leq.

permSort :: Ord a => [a] -> [a]   

Permutation sort with standard ordering <=. Sorts a list by finding a sorted permutation of the input. This is not a usable way to sort a list but it can be used as a specification of other sorting algorithms.

permSortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]   

Permutation sort with ordering as first parameter. Sorts a list by finding a sorted permutation of the input. This is not a usable way to sort a list but it can be used as a specification of other sorting algorithms.

insertionSort :: Ord a => [a] -> [a]   

Insertion sort with standard ordering <=. The list is sorted by repeated sorted insertion of the elements into the already sorted part of the list.

Postcondition:

ys = insertionSort xs satisfies (length xs == length ys) && sorted ys (insertionSort'post)

Specification:

(insertionSort x1) is equivalent to permSort x1 (insertionSort'spec)

insertionSortBy :: (a -> a -> Bool) -> [a] -> [a]   

Insertion sort with ordering as first parameter. The list is sorted by repeated sorted insertion of the elements into the already sorted part of the list.

quickSort :: Ord a => [a] -> [a]   

Quicksort with standard ordering <=. The classical quicksort algorithm on lists.

Postcondition:

ys = quickSort xs satisfies (length xs == length ys) && sorted ys (quickSort'post)

Specification:

(quickSort x1) is equivalent to permSort x1 (quickSort'spec)

quickSortBy :: (a -> a -> Bool) -> [a] -> [a]   

Quicksort with ordering as first parameter. The classical quicksort algorithm on lists.

mergeSort :: Ord a => [a] -> [a]   

Bottom-up mergesort with standard ordering <=.

Postcondition:

ys = mergeSort xs satisfies (length xs == length ys) && sorted ys (mergeSort'post)

Specification:

(mergeSort x1) is equivalent to permSort x1 (mergeSort'spec)

mergeSortBy :: (a -> a -> Bool) -> [a] -> [a]   

Bottom-up mergesort with ordering as first parameter.

leqList :: Eq a => (a -> a -> Bool) -> [a] -> [a] -> Bool   

Less-or-equal on lists.

cmpList :: (a -> a -> Ordering) -> [a] -> [a] -> Ordering   

Comparison of lists.

leqChar :: Char -> Char -> Bool   

Less-or-equal on characters (deprecated, use Prelude.<=).

cmpChar :: Char -> Char -> Ordering   

Comparison of characters (deprecated, use Prelude.compare).

leqCharIgnoreCase :: Char -> Char -> Bool   

Less-or-equal on characters ignoring case considerations.

leqString :: String -> String -> Bool   

Less-or-equal on strings (deprecated, use Prelude.<=).

cmpString :: String -> String -> Ordering   

Comparison of strings (deprecated, use Prelude.compare).

leqStringIgnoreCase :: String -> String -> Bool   

Less-or-equal on strings ignoring case considerations.

leqLexGerman :: String -> String -> Bool   

Lexicographical ordering on German strings. Thus, upper/lowercase are not distinguished and Umlauts are sorted as vocals.