© Stefania Loredana Nita and Marius Mihailescu 2019
Stefania Loredana Nita and Marius MihailescuHaskell Quick Syntax Referencehttps://doi.org/10.1007/978-1-4842-4507-1_16

16. Algorithms

Stefania Loredana Nita1  and Marius Mihailescu1
(1)
Bucharest, Romania
 

In this chapter, you’ll learn how to implement algorithms such as quicksort, mergesort, and bubble sort.

Quicksort

Quicksort is a divide-and-conquer algorithm. Quicksort divides a large array into two smaller subarrays, known as the low elements and high elements. The time complexity in the best case is O(n log n) and in the worst case is O(n2).

The steps are as follows:
  1. 1.

    Choose an element from the array. The element will be called the pivot .

     
  2. 2.

    Reorder the array in such a way that all the elements with values less than the pivot come before the pivot, while the elements with values that are greater than the pivot come after it. After the partitioning process, the pivot is in its final position. This is called the partition operation . The equal values don’t matter; they can go on any branch.

     
  3. 3.

    Recursively you will need to apply these steps to the subarray elements that have smaller values and separately to the subarray of elements with values that are greater.

     
The function qs (quicksort) will take a list [a] of some type a, such that elements of a can be compared with each other (this is specified using the (Ord a) guard). Then, the function will return a list of the same type [a].
qs :: (Ord a) => [a] -> [a]
The quicksort is implemented in Haskell as follows:
qs (y:ys) = qs [x | x <- ys, x<= y] ++ [y] ++ qs [x | x <- ys, x > y]

qs takes as an argument (y:ys), which is a list consisting of the first element, x, and the rest of the list, ys. You apply the list comprehension [x | x <-ys, x <= y] to get a list of all the elements in the list ys that are smaller or equal than y. Next, you concatenate the resulting list with a single element list, [y], and the list of elements that are greater than x.

The recursion in the quicksort algorithm is defined by the function qs, but you still need to finish somehow the recursion at a certain point, so you need to specify the condition when the recursion will end. This is also easily done in Haskell by augmenting the definition of the function qs by adding one more extra rule.
qs [] = []

The algorithms applied on an empty list will return an empty list.

By combining everything, you get the complete quicksort implementation in Haskell, as shown here:
qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (y:ys) = qs [x | x <- ys, x<= y] ++ [y] ++ -qs[x | x <- ys, x > y]
Prelude> qs [1,2,7,8,9,5,3,3]
[1,2,3,3,5,7,8,9]

Mergesort

Compared with quicksort, mergesort is a little more complicated during the implementation process. The time complexity is O(n log n). The algorithm steps are as follows:
  1. 1.

    The list is divided into two parts.

     
  2. 2.

    The two parts are sorted by the algorithm.

     
  3. 3.

    The sorted parts are merged by a special merging procedure that is dedicated to sorted lists.

     
Here is the procedure for splitting the list into two parts:
ms'splitinhalf :: [a] -> ([a], [a])
ms'splitinhalf ys = (take m ys, drop m ys)
      where m = (length ys) `div` 2

Let’s analyze this code. The function ms'splitinhalf will return a pair of arrays into which the original array was divided into two. The m is equal to half of the length of the array, and the standard functions take and drop are used to get the first m elements of the list take m ys and the rest of the elements of the list after those first elements that are used with drop m ys.

Next, you have to define the function that merges the two sorted arrays.
ms'splitinhalf :: [a] -> ([a], [a])
ms'splitinhalf ys = (take m ys, drop m ys)
      where m = (length ys) `div` 2
ms'merge :: (Ord b) => [b] -> [b] -> [b]
ms'merge [] ys = ys
ms'merge ys [] = ys
ms'merge (y:ys) (x:xs)
      | (y < x) = y:ms'merge ys (x:xs)
      | otherwise = y:ms'merge (y:ys) ys
The function will receive two arrays and will produce one array of the same type. The algorithm for merging is as follows:
  1. 1.

    If the first list is empty, [], the result of the merge function is the second list, ys.

     
  2. 2.

    If the second list is empty, [], then the result of the merge is the first list, xs.

     
  3. 3.

    Otherwise, you will return the first elements of the lists and append with the colon (:) function the least of them to the new list, which is the result of merging the two remaining lists.

     
After you have defined the functions ms'splitinhalf and ms'merge, you can easily define the function mergesort.
ms :: (Ord a) => [a] -> [a]
ms xs
    | (length xs) > 1 = ms'merge (ms ls) (ms rs)
    | otherwise = xs
    where (ls, rs) = ms'splitinhalf xs

Now, if the length of the list is bigger than 1, then you follow the default steps of the algorithm. Otherwise, the list with a length of 1 will already be sorted, which represents the condition for ending the recursion.

The complete code for the mergesort is shown here:
ms'merge :: (Ord a) => [a] -> [a] -> [a]
ms'merge [] xs = xs
ms'merge xs [] = xs
ms'merge (x:xs) (y:ys)
    | (x < y) = x:ms'merge xs (y:ys)
    | otherwise = y:ms'merge (x:xs) ys
ms'splitinhalf :: [a] -> ([a], [a])
ms'splitinhalf xs = (take n xs, drop n xs)
    where n = (length xs) 'div' 2
ms :: (Ord a) => [a] -> [a]
ms xs
    | (length xs) > 1 = ms'merge (ms ls) (ms rs)
    | otherwise = xs
    where (ls, rs) = ms'splitinhalf xs
Prelude> ms [1,3,4,1,2,23,7,8,5]
[1,1,2,3,4,5,7,8,23]

Bubble sort

For a bubble sort operation , you change the placement of the element pairs, while there is still a pair of elements (x,y) such as x > y. The time complexity for the worst case is O(n2), and for the best case it is O(n).

You will define a function that will iterate through all the elements in a list, and it will switch the pairs of the unsorted elements.
bs'iter :: (Ord a) => [a] -> [a]
bs'iter (x:y:xs)
    | x > y = y : bsiter (x:xs)
    | otherwise = x : bs'iter (y:xs)
bs'iter (x) = (x)
Prelude> bs'iter [2,1,3]
[3,2,1]
Next, you just need to apply the next function n times. The function represents the length of the list that should be sorted.
bs :: (Ord a) => [a] -> Int -> [a]
bs xs i
    | i == (length xs) = xs
    | otherwise = bs' (bs'iter xs) (i + 1)
bs :: (Ord a) => [a] -> [a]
bs xs = bs' xs 0
Prelude> bs' [3,2,1,5] 4
[3,2,1,5]

You can do this by defining the function bs', which will take two arguments: the list and the number of the current iteration, which is i.

This transforms the iteration into a recursion in such a way that bubble sorting will become a recursive algorithm (just for this example, because the bubble sort is not recursive like the original definition).

Summary

In this chapter, we discussed the three most important algorithms used for sorting: quicksort, mergesort, and bubble sort. We presented their implementations by providing the shortest and most flexible versions of how they can be implemented.

Reference

  1. 1.

    Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.

     
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.135.186.12