This is the first article, in a series of 3, on which we will talk about Sorting Algorithms with tons of charts. On this first one, we will also explore asymptotic complexity in general. We will also have a playground at the end of the article, running async JavaScript code on a Cloudflare Worker, so you can experiment with the algorithms live. You will be able to experiment some stuff (check it later).
The JavaScript code runs on a Cloudflare Worker, called from the page. The graphics data were generated with a code written in C, compiled with GCC version which can be downloaded in this zip file containing the CSV data used as input.
Reading complexity off a chart
First, we must analyze and understand the (read theta) asymptotic notation of some simple functions. To do so, we must find a given value , which when applied to another function of the same complexity, will make the former lie between them, that is, we have a function with a higher asymptotic value and another with a lower one. We will have some charts to help us understand what is going on (I won’t say it won’t have math in some of them). Hover over a chart to read the exact values, especially in those where we can barely see a difference between the lines.
This one can easily be seen in the chart below. We used 40 and 60 as an upper and a lower constant, but we could use anything just a bit higher or lower than 50 to show that this function has a complexity of . As you can see this complexity is noticeable since the origin, making our value , which is the lower threshold for the notation, to be 0.
This one can also easily be proven to have a complexity of . If you could zoom in closer to (you will eventually, but I’m not paying MUI Pro yet), you would see how curve is higher than , but the later overcomes it really soon, between and .
As you can see, the purple curve (the one which is interesting for us) is just a little bit higher than the blue one, but it will be higher than it forever, increasing its margin little by little, making our complexity, as stated before, .
This is a easy one. Just looking to the chart we can see it has a complexity, because , so we can treat as a constant.
That’s a tricky one, because as you can see the purple curve goes below the yellow one (it even goes negative!) for a long time, intersecting it only at (you can verify it by calculating ), but as , we have a time complexity of .
Maybe you cannot see the complexity of this formula right away (I didn’t), but we can prove it with what we learned in our Calculus classes, as soon as we realize that a limit solves it with mastery, as . In conclusion, our time complexity is constant, this is .
We need to go further with this chart to see something. Trying to see that it has a time complexity of is a bit hard with a chart, as is REALLY slow, but with a chart going until we are able to see something. With math, we can see that the purple line overcomes the blue one at , but we are unable to see any difference in the chart until something around .
The basic sorting algorithms
In this first article, we will analyze the basic sorting algorithms: Bubble Sort, Insertion Sort (with its variant) and Shell Sort (with different ‘sequences’). All the analysis will be made sorting arrays of unsigned integers, using two languages: C (which will have a better performance, in most cases - although not in all cases) - the chart language - and JavaScript - the playground language. We will analyze the time spent to sort the array, as well as the changes/swaps needed to do it. For Sorted and Reversed arrays, the benchmark was run only once, but to generate the Random data, each data sample was run times or minutes, whichever took less time, so that we were able to make something like an average, to avoid samples where we got a more or less ordered random arrangement of values in the array.
Another point about the random array generation is that its allocation + filling-the-array-with-values time was taken in consideration in the time measure (for the sake of comparison it doesn’t matter as every sample has that extra “linear” time).
Disclaimer: Some weird values can be seen in the sorted array examples, partially because we just ran it once, and it could have been blocked by some OS interruption, taking longer than it would be expected, looking to us like a strange and unexpected curve in the chart.
Bubble Sort
With a time complexity of , this algorithm is probably one of the worst algorithms for sorting (we can find something worse, like BogoSort or SleepSort 💤 (in Portuguese because it doesn’t exist in the English Wikipedia somehow?), as it takes a LOT of time to organize an array of values, as it compares adjacent pairs of numbers to see if they are in relative order.
We used arrays varying from until to generate the data below. The left y-axis shows the time and the right one shows the swaps. Use the toggles above each chart to switch between random, reversed and sorted input. As a reminder, the sorted charts may be a bit wrong in the time dataset, as explained before in this report (TLDR: OS interruptions can cause this).
The code used for it can be seen below, followed by the charts showing the data.
long long int bubbleSort(int *C, int n){ long long int changes = 0; int m = n-1, k = 1, changed, i, temp;
do { changed = 0; for(i=0; i<m; i++) { if(C[i] > C[i+1]) { temp = C[i]; C[i] = C[i+1]; C[i+1] = temp;
k = i; changed = 1; changes++; } } m = k; } while(changed);
return changes;}Some information we can retrieve from these charts is that BubbleSort has best case complexity of as it will only run through the array once, and stop, this is why it only makes changes and has such a small running time (0?). Reversed case really shows us why he has such an asymptotic curve, going from in the size to incredible with a size of (x bigger size, x bigger time, as we would expect with a complexity). To have some fun, you can try to switch the y-axis scale back and forth between linear and logarithmic scale, to see some difference.
Insertion Sort
Let’s move on to another simple sorting algorithm which we all learned in our 1 year of CS. It also has a time complexity of , but we will be able to see some evolution, comparing to Bubble Sort.
For these charts, we also used arrays varying from until to generate the data below. All blah-blah-blahs spoken about the BubbleSort are also valid here.
The code used for it can be seen below, followed by the charts showing the data.
long long int insertionSort(int* C, int n){ long long int changes = 0; int i, j, key;
for(j=1; j<n; j++) { key = C[j]; i = j-1; while(i>=0 && C[i] > key) { C[i+1] = C[i]; i--; changes++; } C[i+1] = key; }
return changes;}I really like the Insertion Sort idea, it’s really a pity that it’s worst-case complexity 😞. The reversed chart shows us that it makes exactly the same changes as BubbleSort in reverse order, although it took less time, so point to Insertion ✨. In random data, it also runs A LOT faster than Bubble sort (in this sample case, almost 3X faster). So, although both have an average-case time complexity of , it will only be the same asymptotically, as in “small” samples Insertion can be really faster.
Binary Insertion Sort
Now we will have a kind of evolution of the Insertion Sort Algorithm. As we are searching the place to insert our new number, in an already ordered array, it is pretty easy to think about a binary search (maybe one day I could try to implement it with a ternary search - really don’t know if it would be faster) to find the exact place where we should insert our number. So, let’s see how the thing goes.
Again, arrays size varying from until to generate the data below. I could have used a bigger data sample, because as you will see, this is a bit faster than the last two, but to keep the comparison between them, we used the same data sample.
The code used for it, as well as the code used in the binary search, can be seen below, followed by the charts showing the data.
int binarySearch(int* data, int low, int high, int key){ int mid = low + ((high-low)/2);
if (low == high) return low; else if (key > data[mid]) return binarySearch(data, mid+1, high, key); else if (key < data[mid]) return binarySearch(data, low, mid, key); else return mid;}
long long int binaryInsertionSort(int *C, int n){ long long int changes = 0; int i, key, position;
for(int j=1; j<n; j++) { key = C[j]; i = j-1; position = binarySearch(C, 0, j, key); while(i>=position) { C[i+1] = C[i]; i--; changes++; }
C[position] = key; }
return changes;}As you can see, the changes occur exactly the same number of times both in Normal and Binary Insertion. The great advantage comes when we don’t need to compare as many times as we would compare in a normal Insertion Sort, because we can find the place we must insert ourselves in time, saving us something around 30% of time, although having an average-case time complexity of , exactly the same as Bubble and Insertion Sort.
Shell Sort
Let’s start talking about the Shell, thinking about the Insertion. What is it really good at? Sorting ALMOST sorted stuff! And that’s what the Shell sort abuses of, making the array each time more “sorted”, making it faster to get fully sorted.
It uses something called sequences to order different pieces of the array at the same time (you can see “all” of them here (at least, the more famous ones)). Here we used three different sequences, as follow:
- Shell Sequence (1, 2, 4, 8, 16, 32, …)
- Knuth Sequence (1, 4, 13, 40, 121, 364, …)
- Tokuda Sequence (1, 4, 9, 20, 46, 103, …)
It is expected that each sequence makes the ShellSort faster (although, as we will see, the last two have just a small difference, not exactly one being better than the other), as they tend to decrease their time-complexity, with the Tokuda Sequence having a time-complexity not yet calculated, but probably better than the Knuth one ( - too hard I know).
This time, arrays size will vary from until to generate the data below, to all the sequences.
The code used for it can be seen below, followed by the charts for each sequence and input order. The gap sequence generation will be omitted for sake of brevity.
long long int insertionShellSort(int *C, int n, int h, int offset){ long long int changes = 0; int i, key;
for(int j=offset+h; j<n; j+=h) { key = C[j]; i = j-h; while(i>=0 && C[i] > key) { C[i+h] = C[i]; i-=h; changes++; } C[i+h] = key; }
return changes;}
long long int shellSort(int *C, int n, int typeSequence){ int numElems; int* sequence = generateGapSequence(n,typeSequence,&numElems);
long long int changes = 0; int i, h, offset;
for(i=numElems-1; i>=0; i--) { h = sequence[i]; for(offset=0; offset<h; offset++) { changes += insertionShellSort(C,n,h,offset); } }
free(sequence);
return changes;}Wow, we have a lot of data here! As you can see, ShellSort is pretty BAD at sorting already sorted arrays in comparison to the others sorting algorithms (you can see a comparison in the charts below). That would be easily solved by adding a check to see if it is already sorted (although, it wouldn’t solve “almost sorted” arrays’ long running time). A HUGE improvement can be observed in the last two, as they only take roughly 0.1s to sort the same thing Insertion took 43 seconds!!!!11!.
Weirdly enough, Knuth’s and Tokuda’s sequences got pretty close not exactly saying which one is better, which is plausible, as Tokuda one doesn’t have a time-complexity well-established. Anyway, we will have some comparisons to see that difference better in some charts below.
Putting them side by side
This is over for today! Hope you enjoyed the article, and that it gave you some insights other ones didn’t give you, as it took a lot of code and time from me. Wait for similar stuff for the other sorting algorithms! Take a look in the charts below, with some direct comparisons between the different sorting algorithms, remembering that the three algorithms only have data until size , while the three Shell ones go up until .
Playground
These algorithms were also “translated” to JavaScript, which you can play with in the table below. The sorting itself happens on a Cloudflare Worker rather than in your browser, so the numbers do not depend on what your laptop is doing. One caveat on the Time column: the Worker cannot time itself, because the runtime freezes its clock during synchronous execution as a side-channel mitigation. What you see is the full round trip measured from the browser, which includes network latency - so expect a floor of roughly a tenth of a second no matter how trivial the array, and treat small numbers as noise. Arrays are capped at 25,000 elements, since the quadratic algorithms exceed the Worker CPU budget above that. The times will be slower than the C ones used for the graphics above, but if you run the same code locally you will see that asynchronous JavaScript makes the sorting algorithms REALLY faster when using Bubble or Insertion sort, although it makes the Shell algorithm slower (we can’t process a lot of things at the same time, as we must make all the different sequence values of in strict order). Hope you enjoyed, and see you next time!
No runs yet. Pick an algorithm and an input, then press Run.
This article was first written as a report for the Data Search & Classification 📊 Subject at the CS Bsc. course at UFRGS, and adapted to this blog post. You can find the original post with the API running on a Node.JS backend (some order of magnitude faster than this one up here) on this repo on my Github.