Recently I've been doing some coding in Python but I felt like I didn't really understand what was going on. So as a way to better understand python's syntax and semantics I implemented a couple of the better known sorting algorithms - for fun and the greater good! This post showcases the code I wrote and talks about the hurdles I encountered while implementing the algorithms. This post is only meant to document my learning process of Python implementations and not really meant for learning about the mathematics behind the space- and time complexities of the different sort algorithms as I had already done that in my EE undergrad. All comments about implementation issues, bugs or pythonic styling are more than welcome!
The simpler sorts
As a start I decided to go with the simplest looking sorts, insertion- and selection sort. They are both O(n^2) in time complexity and thus rarely ever used on large datasets. Their implementation is however straight forward. It is noteworthy to point out that I wanted each function to return a new list of numbers and that the functions shouldn't mutate the list passed in at all.
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. - Insertion sort
The search iterates through the unsorted array. Each time it passes on of its elements to an inner function insert_item, which takes a list and element and inserts the element in the right place (as dictated by the passed in function sort_by).
The sort_by function takes as a default an lambda function
(lambda a, b: a < b). To those of you who haven't heard about the built-in lambda functions I encourage you to check them out. They can come in handy to build up simple functions in a lucid manner, when using def is simply too much.
The algorithm [selection sort] divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. - selection sort
My implementation starts off with the passed-in list and copies all elements from the list into a new place in memory (very important so that we don't mutate the passed in list) and assigns that object to the variable initial_list. Then we iterate through that list and at each passing we find the "lowest" element as dictated by the sort_by function as before. We then append that element on the back of our sorted_list object and voilá! after passing through the outer loop once we have sorted the list passed in. We then return.
The more efficient sorts
Going on down the sorting algorithms difficulty-ladder we next encounter sorts with O(n log(n)) time-complexities. Here is where recursion comes in and the implementations begin to become more interesting and non trivial.
Conceptually, a merge sort works as follows:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list. - Merge sort
Merge sort was invented in the time of the tape machines by the legendary mathematician Jon von Neumann.
My implementation gets straight to the point. First we split the list into single element list and then merge those small lists recursively so that at each point the smaller sub-lists are individually sorted. The function that has the merge functionality is maintained within the merge_sort function itself for brevity and as not to dirty our global name-space.
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. - heap sort
The abstract description of heap sort may make it seem a little daunting but it really isn't much more complex than merge sort at all. The functionality I had to implement was heapify, take a list and make a heap data structure out of it and sift_down, a function that returns a heap into a legal state when the top element has been removed from it.
My implementation goes like this: First create a heap using the heapify function, basically placing each item of the list at the bottom of the heap and then sift the elements up (incorrect elements down) until the inserted element is at a place so that the heap is valid. Next I remove the top node of the heap, which we know will be the lowest/highest/which ever way you want to sort your list, place it in a new sorted_list and then we make the heap valid again. We continue this procedure until there are no leafs left in the heap.
Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:
- Pick an element, called a pivot, from the array.
- Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values. - Quick sort
I proceeded using a similar approach as I did in merge sort, the functions that do the heavy lifting are maintained within the quick_sort function itself. The implementation follows directly from the description on Wikipedia and I was lazy so I just chose the last element to always be the pivot in each sub-list that is to be sorted.
One thing I noticed is that the python interpreter will throw the error
RuntimeError: maximum recursion depth exceeded in cmp if the test cases I tried were too large. This doesn't mean that my implementation is buggy but simply that the interpreter has a default recursion depth which can be modified by the user. More about that here
These implementations were much easier than I had imagined and I didn't really have any big problems. Next up: code a Search class, implement the different algorithms there and do some testing! I also want to try and implement some of the AI search algorithms (A*, minimax & alpha-beta pruning).