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).
- 1.
Choose an element from the array. The element will be called the pivot .
- 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.
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.
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 algorithms applied on an empty list will return an empty list.
Mergesort
- 1.
The list is divided into two parts.
- 2.
The two parts are sorted by the algorithm.
- 3.
The sorted parts are merged by a special merging procedure that is dedicated to sorted lists.
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.
- 1.
If the first list is empty, [], the result of the merge function is the second list, ys.
- 2.
If the second list is empty, [], then the result of the merge is the first list, xs.
- 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.
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.
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 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.
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.