Exercises: Sorting
Apr 162018Before attempting these exercises, you should read the posts on comparisons and swaps, iterative sorting and recursive sorting.
Recursive Sorting
Apr 162018In the previous post we saw two iterative sorting algorithms: selection sort and insertion sort both work using a loop to put the right values in the right places, one at a time. They are two of the simplest sorting algorithms. But they’re not very efficient — for long lists, they’re too slow.(1)
In this post we’ll see one of the simplest efficient sorting algorithms, called merge sort. Rather than sorting items one-by-one, it works by recursively sorting shorter lists.
Iterative Sorting
Apr 162018Before writing an algorithm, it’s always worth thinking about how you would solve the same problem “by hand”. After all, you can’t write instructions for how to do something if you don’t know how to do it yourself.
The problem we’re currently interested in is sorting — given a list, put its values in order. There are hundreds of algorithms which solve this problem, but ultimately every sorting algorithm does one of two things:
Comparisons and Swaps
Apr 162018We have seen two search algorithms on lists — linear search and binary search. Both algorithms find the index of a given target value in a list. But they make different assumptions about the data in the list: linear search works on any list, whereas binary search only works if the list is in order.