So I got me a sorting algorithm.
I really wanted to create one, just for the exercise. Of course, I did not have any expectations for it to be especially efficient, as I presume all low hanging fruits have been picked.
Well, it turns out we’ve picked up all the extremely low hanging ones, then we learned to reach higher and now we’re trying to pick the high hanging ones, but I suspect there are still unpicked fruits on the lower end.
That’s where my algorithm stands. And a bit to the side.
What’s the situation – crystal sort (as I called it) is generally slow, except for when you have an array with a particular property and you know in advance that it has it (or you strongly suspect that it does).
Quick disclaimer – I spent about two hours googling sorting algorithms, trying to read the basics of all of them. I could not find mine amongst them. My suspicion is that many people have come up with the idea already, but have dropped it due to it’s shortcomings. I am happy enough with the idea even though it’s not optimal, so I’m trying to make the most of it. It deserves the light of day (some light of day), even though it’s not groundbreaking.
So… I was mulling over the general sorting problem (well, the linear sorting mostly, iterations + swaps) and I was thinking about the eponymous bubble sort, used for the “low bar” benchmarking (along with shuffle sort, I guess).
I was thinking about how we keep the bubble sort around as an example and that every time you look at it you have to ignore the obvious optimizations, just so that you have it remain a pure example. Specifically, I was thinking about how you always swap adjacent elements of the array, disregarding the question “does this swap put at least one of the elements in it’s correct position”. So I decided to code that as an exercise and to my delight I found that it’s performance is… not abysmal.
Generally what happens (or happened in that first version) is that you go through the array and compare your current element with the first and the last one. You swap it with the first one, if the current one is smaller. Otherwise, you swap it with the last one, if the current one is larger. Very, very simple, yet at the end of the pass you are guaranteed to have both the smallest and largest elements of the array at their exact correct and very final positions. Then you simply do the same for the remaining elements between them until you run out of remaining elements.
This proved to be so elegantly simple that I had to make an effort to “properly” code it – to be efficient, optimized and beautiful module. I did some comparisons (using ready-made code for other algorithms, lifted from the internet) and to my delight I found that it performed on par with selection sort (technically a tiny bit better, but within the efficiency margins that I suspect strict code optimizations govern; meaning – hard code overclocked code may cause the comparison to change a bit).
So… I was happy, but I realized the algorithm, as it was, had a major built-in inefficiency. Say you make one pass over the array and you get your smallest and largest elements at the first and last positions. Within the remaining elements you can have ones that have the same values, just scattered around. And in subsequent runs you’ll find them and place them where they belong, but the algorithm has no memory that it has already found those values, so… it seems like a missed opportunity. What if you could dispose of them quicker.
So I added another, secondary operation in between the primary iterations. After each primary pass, when you have found the min and max of the current subset, you go into the remainder and extract all values equal to those min and max and add stick them in their proper places. Then and only then you make another primary pass, finding new (and unique) min and max.
Result? Well, you have to consider the business case. Sorting algorithms are mostly used for small arrays with largely varying values. But if you, for some reason, want to sort an array that you know (or strongly suspect) has multiple duplicate values… well, then you better use insertion sort. But seriously, if you want, you can use my algorithm. It performs better and better the more duplicate values you have. In extreme cases (as I just suggested) it performs almost as well as the insertion sort.
For something botched together around almost non-existing expectations, I’m pretty happy.
Some disclaimers, again: The code that I used for comparison was lifted from https://stackabuse.com/sorting-algorithms-in-python
I presume the level of code optimization is the same between the different sorting methods (for a fair comparison between them), but also they are optimized for readability, as the blog post is supposed to be educational. So the different methods may turn out to have significantly different rooms for optimization, so if you choose performance over readability and refactor everything, the results may differ.
Also: The current code of my own algorithm is… well, I tried to keep it code neutral. Meaning I chose to keep an “iteration + swap” version, in order to exclude anything that is python specific. So it could be a bit faster with list comprehension.
Keeping that in mind, I can’t resist but try it that way – comprehend my lists to the max to see what would happen. I’ll add an update, once this is done and evaluated.
Last (apparently), but not least:
The algorithm is called crystal sort, because of the way the sorted values crystalize from the ends of the array towards the middle. It just reminds me of crystallization.
And yeah, here is the repo, actually 🙂