Sorting Algorithms
One of the first things you might learn in a computer science class are data structures and algorithms. So I thought that a fun way of learning the C programming language could be to write a bunch of sorting algorithms from scratch. It got out of hand.
What it can do
The base sorting program has this functionality:
Provide a library of sorting algorithms. If you include the files, you’ll get access to some functions for sorting integers. These can be called individually, in which case you’ll get the stats for one of the sorting algorithms.
New algorithms. There are a few algorithms that I’ve made up along the way, including Hanoi Sort, Poker Sort and In-place Merge Sort.
Run tests. There is a function for sorting a lot of integer arrays to make sure that everything is working. It first sorts a 5-element array, and then 10 elements and so on until a maximum of 300. Slower algorithms have this capped at a lower number, since sorting a 300-item array using some of these algorithms will take longer than the age of the universe.
Export stats. There is an option to run the algorithm many times and get stats for it. It can be done by either running the algorithms many times with different array lengths to test time complexity, or it can test one algorithm many times to test standard deviation.
What it can’t do
Missing some merge sorts. Some of the merge sorts on the Wikipedia page are just merge sort but adapted to different hardware like tape decks or when the data to sort is larger than available RAM and it needs to be split.
Missing hybrid sorts. I excluded hybrid sorts from this project because they’re really just a mix of two other sorting methods.
Sort any data type. This is made exclusively to sort arrays of signed 32-bit integers.
N64 visualiser
The N64 visualiser (or Sort 64) is an N64 demo that shows a visual representation of how the sorting algorithms work. You’ve probably seen them before somewhere on Youtube.
You can find out more about it on its own sub-page. (Coming soon)
Sorting algorithms
There are 53 sorting algorithms, which can be sorted into several categories based on the methods they use to sort their elements. This is generally following the Wikipedia categorisation methods.
Exchange sorts
Exchange Sorts are sorting algorithms that reply on exchanging elements with each other. Not all exchanges put each item in its correct place, but they do move it closer to its final position.
- Bubble Sort
- Comb Sort
- Cocktail Sort
- Hanoi Sort
- Proportional Exchange Sort (this one isn’t working proplerly in the current configuration)
- Quick Sort
- Slow Sort
- Stooge Sort
Insertion sorts
With the exception of Insertion Sort and Gnome Sort, these algorithms reply on putting the elements onto a separate data structure where it is sorted and then reinserted into the initial array.
- Cube Sort
- Gnome Sort
- Insertion Sort
- Library Sort
- Patience Sort
- Shell Sort
- Splay Sort
- Stalin Sort
- Tree Sort
Selection sorts
These algorithms are similar to exchange sorts, but put every element in its final position with minimal swaps.
- Bingo Sort
- Cartesian Sort
- Cycle Sort
- Heap Sort
- Pancake Sort
- Selection Sort
- Smooth Sort
- Tournament Sort
- Weak Heap Sort
Random Sorts
As the name implies, these are algorithms that rely on some sort of randomness (with sifting) to sort their arrays.
- Bogo Sort
- Bozo Sort (Dumb)
- Bozo Sort (Smart)
- Brute Force Sort
- Goro Sort
- Poker Sort
Concurrent sorts
If you want to take advantage of multi-threaded processing to sort your lists, you can use concurrent sorts. Though my implementations are single-threaded though, so they’re essentially just exchange sorts.
- Batcher’s Odd-Even Sort
- Bitonic Sort
- Odd-even Sort
- Pairwise Network Sort
- Sample Sort
Merge sorts
These algorithms rely on taking two sorted sub-lists and merging them together.
- Merge Sort
- In-place Merge Sort
- Quad Sort
- Twin Sort
Distribution sorts
Distribution Sorts read the actual numbers and perform calculations on them to determine their place in the array instead of using anonymous comparisons.
- American Flag Sort
- Bead Sort (Fast)
- Bead Sort (Slow)
- Burst Sort
- Bucket Sort
- Counting Sort
- Flash Sort
- Interpolation Sort
- Pigeonhole Sort
- Proxmap Sort
- Radix Sort (LSD)
- Radix Sort (MSD)
Development background
This project was partially inspired by learning about time complexity on a video by Udiprod. I wanted to learn as much about the speed of different algorithms to be able to compare them to each other.
The other motivation was though my work. My professional background is in business and Marketing but I’ve always loved to do programming on the side for fun. I started working software development full-time a few years ago and the senior director of the division was and old-school programmer who would often tell stories about how back in his day they’d have to write their own bootloaders and kernels and us kids don’t know how easy we have it.
So I took it upon myself to start from scratch by going back to basics: algorithms and data structures. Something that I noticed was that sorting algorithms tended to include a whole lot of different practices that were useful in C-level software – Pointers, structs, recursion etc. This made it a great way of learning the language.
I started off with the most common algorithms like Insertion Sort, Bubble Sort and Quicksort but after looking up the sorting algorithms page on Wikipedia, I found that there were a lot more than I originally expected. So I decided to reproduce all of them in C.
I went through the list one by one until they were all done. I had to skip a few because they weren’t meant to be used to sort arrays in particular, but most of them were completed correctly. I carried on working on this for about a year, making a total of 53 algorithms or about one per week.
In between, I also added some additional functionality, like a data structures submodule, a unit tester for each algorithm and an exporter for tracking speeds. There’s also a bunch of arguments that can help determine these settings, visible when you type in --help.
After all that, I gave the project a break and started working on the Libdragon tutorial to help people learn how to make games on the Nintendo 64. However that was only a temporary setback as soon after I started work on Sort 64, a Nintendo 64 demo that works as a graphical user interface to all of these sorting algorithms that I previously wrote.
This required an extensive rewrite of the algorithms in order to make them compatible with a visualiser, but in the end it worked out like I hoped it would. The only main issue is that about a third of the algorithms had to be excluded because they relied on external data structures that could not be visualised.
Once that was done, I decided to complete the final part of the puzzle, which is to publish my findings for each algorithm on n64squid.com since I found that people don’t really talk about the specific time complexities or their distributions online. This section is still under construction, so please be patient.
