In my previous article, I have dealt with what an algorithm is and provided an overview of a breadth-first search algorithm. Embarking on the challenge to learn different algorithms, I have decided to move onto something very simple this time. Well … simple to implement.
Sorting algorithms (or in other words sets of procedures), are used to ensure a certain order of elements, typically in a list. Sorting has been attracting a lot of attention from the early days of computer engineering. Being a thing of value (sorting has multiple computer science applications) and at the same time difficult, had spun tens of different approaches and a multitude of scientific papers. Like one of the first quoted below, as early as 1950’s.
Sorting, the process of arranging numbers in a monotonic sequence, is an activity common to many data processing systems. This dissertation is a theoretical study of the fundamentals of sorting. In particular, it deals with the problem of minimizing the time required to sort data (items) with electronic equipment.
ELECTRONIC DATA SORTING, DEMUTH, HOWARD B.Stanford University, ProQuest Dissertations Publishing, 1957. 0020444.
Having a list of items sorted within as short time period as possible, while keeping computation and memory usage low, are the keys to science of sorting. To call something a sort algorithm, it needs to meet the following criteria:
- each element is no smaller than the previous element according to the desired total order
- The output is a reordering of the input.
The one I have decided on today, is one of the simplest. The bubble sort. Sometimes also known as the sinking sort. Bubble sort is one of the most inefficient ways of sorting an array or a list. Though it is very simple in concept.
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list.
https://en.wikipedia.org/wiki/Bubble_sort
Before we head onto the code, I still have two more things to discuss. First of which is sorting algorithm stability. A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. In simple words, if we’d have a class, where each pupil has a number identifying them, their firstname and lastname. Say some of these pupils have the same firstname and we chose it to be the key to sort. A stable implementation will ensure these two items will leave the sorting algorithm in the same sequence they have entered. This is important if we’d like to sort the list again by id. In a stable version, we will not impact anything that is not related to the original key, so that every each search attempt by a different key, just makes the list more ordered and avoids shuffling elements again.
The bubble sort is a stable sorting algorithm.
But I have promised two things. The second one was me looking for a good visualization of what the bubble sort algorithm might be doing. And what could be better than watching a nice video of bubble sort done with some Hungarian folk dance?
Jumping into some coding, I’ll be leveraging the same, one and only Codingame. I have selected what I thought to be a ‘simple’ example game. I only managed to succeed in completing one out of 5 test cases though. It might be I did not get it. Anyway, the piece of work can be found here. It works, it sorts and it is using bubble sort.
This one is also interesting, as it is not a simple integer bubble sort, but is sorting dictionaries ascending or descending. I have cheated on the descending one slightly :). The main loop is found below.
class BubbleSort:
def sort_items(self, expression, elements):
output = elements
if expression["direction"] == ASCENDING:
output = self._sort_ascending(output, expression)
else:
output = self._sort_descending(output, expression)
eprint(f"Sorted list: {output}")
return output
def _sort_ascending(self, input, expression):
output = input
length = len(output)
for i in range(length-1):
for j in range(0, length-i-1):
if output[j][expression["sort_by"]] > output[j + 1][expression["sort_by"]]:
output[j], output[j+1] = output[j+1], output[j]
return output
# a blasphemous cheat!
def _sort_descending(self, input, expression):
return sorted(input, key=itemgetter(expression["sort_by"]), reverse=True)To be fair, I have also learned a few valuable lessons on python with this exercise. This is:
- you can compare strings as numbers in python (neat!)
- The power of the filter
- You can actually sort a dictionary in one-line command without using lambdas
Now moving on to deciding on O numbers. The examples in the table below unfortunately point at quadratic time complexity (as in number of elements impacts time to complete as O(pow(n,2))). The memory usage is interesting and seems to be dependent on both elements and number of runs. Still it stays linear here (O(n)).
| Number of list items | Number of runs (desc/asc) | Time elapsed (s) | Memory usage (kB) |
| 3 | 1 | 0.00065 | 6924 |
| 6 | 2 | 0.005 | 6920 |
| 33 | 2 | 0.008 | 7084 |
| 62 | 3 | 0.014 | 7088 |
| 7 | 4 | 0.004 | 7088 |
Still a bit frustrated I got the exercise wrong!
The bubble sort is one of those nightmare’s your University Computer Science Professors love to use for examples, but it is just impractical to apply. In my implementation, I am using a standard approach. If you’d like to experiment, I highly encourage you to review this article on the optimized python bubble sort version.
The key learnings then are:
- Sorting algorithms are being reviewed and researched since early 1950’s
- Bubble sort is one of the first documented
- Bubble sort is inefficient
- It is not worth it for you to look at bubble sort long-term
- Bubble sort can be explained in Hungarian folk dance
And as we have reached the end, here is Sorting Out Sorting, a pretty nerdy, but good to watch youtube video on different ways of sorting:
Gustaw Fit 