Is this the simplest (and most surprising) sorting algorithm?
arxiv.org
arxiv.org
The inner loop takes an array and an index i in the array, and rearranges the array to put the largest value at index i. This is done in such a way that if the sub-array up to but not including i is sorted, then afterwords the sort will be extended such that the sub-array up to and including i will be sorted.
The outer loop says, just call in to the inner loop with i from 1 to n. This will result in a sorted array, because the initial array of a single element is trivially sorted, and then we'll have by the sort-extension property of the inner loop that the progressively larger sub-arrays of 2, 3, ... up to N elements become sorted.
You can see that the inner loop has the sort extension property by thinking about two cases.
Case 1: If the i-th element is already larger than all previous elements, it won't touch any of the elements before i, and will only potentially make the i-th element bigger, thus clearly extending the sort though the i-th element.
Case 2: If the i-th element is smaller than one of the previous elements, it won't touch any elements until reaching that smaller element; then it will start a series of swaps until it reaches index i, at which point the the original value of the i-th elment is left inserted in sorted position into the sub-array up to and including i. So at this moment we have the sort extension property. From there, it may increase the value of the i-th element and change later elements, but of both those will preserve the sub-array sort.
It's basically insertion sort, but with the curious property that the last value of the sorted subarray immediately and always has the correct value, and we then "gently" insert new values into the sorted subarray.
smusamashah linked to a nice sort visualization.
https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...
Tap the "Insertion Sort" checkbox on the right, and then the "Start" button below that.
You can see how both sorts are slowly constructing a sorted subarray, but this sort has the interesting property that the tail of the sorted subarray immediately obtains its maximum brightness, and new values are gently incorporated into the array, while the insertion sort tail is just the brightest value encountered so far, and the latest value is "abrutly" sifted down into its appropriate place.
It feels like this sort might minimize some kind of "sort entropy" metric? I.e., visually it looks very smooth. Each step along the way to sorted is very small.
That is the most beautiful thing in CS I've ever seen.
Is rain just the atmosphere running bubble sort ;) ?
https://cs.stackexchange.com/questions/45348/why-does-this-s...
And it was answered successfully by pointing the same invariant they point in the paper.
I remember finding this program through via automatic program search, so the algorithm and the question of why it works as probably been discovered many times.
If only we had something that would allow to surface information from the vast amount of data available...
Of course traditional scientific publishing has its place (including the care for methodology and source citation)... but many people will search directly those websites instead, so clearly it's an important emerging source of information and discovery.
You define some elementary blocks like in scratch (Blockly). And you try to randomly assemble the blocks so that they respect the type constraints. And you score your program based on the number of test case it got right.
For this simple problem, naive random search was all that was needed. (less than 100k programs evaluations)
But for more advanced cases you could use something like Genetic Programming with Koza's Automatically Defined Functions where you build an intermediate library of useful blocks.
Now one would use deep learning and produce source code directly with some tool like Copilot and run it until it passes all tests. Or if you want to get your hands dirty, you can re-implement the old school methods and use a neural network to make the pick decisions instead of a random pick.
Once you have programs that pass all test cases, you can try to prove correctness (that's more something like HOL-Light would do) and whether or not they are equivalent (and equivalent to a formal specification) and optimize them further by transforming the program.
OP (2021): https://arxiv.org/abs/2110.01111
Stack Overflow (2021, linked by 'Xophmeister in this discussion): https://stackoverflow.com/questions/69437526/what-is-this-od...
Stack Overflow (2021, linked from previous): https://stackoverflow.com/revisions/69435932/1
Stack Overflow with 5 downvotes! (2020): https://stackoverflow.com/questions/63214115/what-is-the-nam...
Stack Overflow (2020): https://stackoverflow.com/questions/59802669/pointer-array-s...
Computer Science Stack Exchange (2015, linked by 'GistNoesis in this discussion): https://cs.stackexchange.com/questions/45348/why-does-this-s...
Stack Overflow (2014!): https://stackoverflow.com/questions/25276619/how-should-i-an...
Reddit (2014, same as previous): https://www.reddit.com/r/algorithms/comments/2dect7/how_shou...
I always get it confused with self-hosted https://github.com/CoatiSoftware/Sourcetrail but I think Sourcetrail just shut down.
Github (2021): https://github.com/terror/paragon/blob/master/examples/sort.... Github (2012!): https://github.com/ragnraok/VisualSort/blob/master/sortalg.p...
Chegg (year?): https://www.chegg.com/homework-help/questions-and-answers/15...
Apparently this was mentioned in a problem set for MIT edX course 6.00.1x in 2014. Then maybe someone then tried to have the internet do their homework for them (this may also be the case for some of the posts in my parent comment):
Math Stack Exchange (2014): https://math.stackexchange.com/questions/876400/best-worst-t...
Note that the question got 3 downvotes, and that the answer is wrong. In particular, the two sorts in the question sort in opposite directions!
Stack Overflow with 6 downvotes (2019, with incorrect answer): https://stackoverflow.com/questions/57080923/how-to-understa...
Stack Overflow (2016): https://stackoverflow.com/questions/34745203/using-a-for-loo...
Stack Overflow (2016): https://stackoverflow.com/a/37650932
What are you searching for to get these results?
[sort "for (int i = 0" "for (int j = 0" site:stackoverflow.com] https://www.google.com/search?q=sort+"for+(int+i+%3D+0"+"for...
["modswapsort"] https://www.google.com/search?q="modswapsort"
The last is the function name from one of the earlier results.
During college junior year (1993) as a physics major I took a class in digital electronics (which included 68000 assembler programming). We had a lab contest to create the fastest sorting routine for a set of random unique numbers between x and y.
I won the contest by setting to 0 a y-x register range of memory and then inserting each number into the range based on the number itself ("27" into register 27, "18" into register 18, etc.). Then I printed out all non-zero numbers in the range.
The other 20 or so students did versions of bubble-sorting and called my solution a cheat. The professor defended my victory as I had not broken any of the rules of the contest...
Although if it took a long time to enumerate the list of elements…
In my case, though, the teacher disqualified my solution since the resulting lists didn't contain the same fixnums as the one i sorted, which I argued was stupid.
In the end I implemented a merge sort with some tricks and won anyway.
Arguing was futile. When we started benchmarking very large lists, the counting sort was the only one that did it in reasonable time. Despite being disqualified.
Hahahahaha :D
> I won the contest by setting to 0 a y-x register range of memory and then inserting each number into the range based on the number itself ("27" into register 27, "18" into register 18, etc.). Then I printed out all non-zero numbers in the range.
That's really smart. The others were just angry because they couldn't think outside of the box. Nice work!
Our snake code ran at something obscene like 1,000 Hz. So much faster than anyone else’s. The professor couldn’t understand how we did it, so gave a low mark.
I didn’t pass because the point of the assignment was to use lookup tables, even though that was a more complex approach in this case :(
Are you sure about easy to calibrate 8) Did your solution have the same level of accuracy across the range as the MCU would provide?
Bizarrely, you sometimes have to follow the standards because that is what everyone does. I can't think of an example now but there will and have been cases in engineering where the wrong answer is the right one because that is what is done. I know of mensuration devices that "model" some curves with a linear approximation and paper over the errors with cough error estimates and/or keeping within the nearly linear range. That too is fine if everyone understands what is going on.
Accuracy is a funny old thing.
However, I like your approach and it shows you probably understand the principles involved. Ideally, if you are going to be a smart arse like that, then submit two solutions - the proscribed one and your clever one.
You mention a MCU but not what sort of sensor ...
That was genuinely upsetting to read.
Teacher was like, nah, that's not possible, and clearly hadn't even read it. Gave me an A just to stop me complaining, still not understanding the project.
And don't you mean "27" into register 27-x, do. 18 etc.?
Much faster to find upper and lower bounds and essentially construct a hash table than to manually sort a whole list of non-trivial length.
I think the mainstream sorting algorithms tend to cater towards "mainstream" ordering which tends to be somewhat sorted versus purely random. An example is https://en.wikipedia.org/wiki/Timsort
Hey! That's my sorting algorithm! (Well, I'm sure it has been independently discovered many times, but one of those times was by me before I had learned of O(n log n) sorting; I used it many times including in the INOI 2004 programming contest, about which I asked the following question ten years ago in 2011 on math.SE about this algorithm and Catalan numbers, a truly surprising property that is not mentioned in this paper: https://math.stackexchange.com/questions/36022/how-do-the-ca...
> For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following:
//Given array a[1], ... a[n]
for i = 1 to n:
for j = i+1 to n:
if a[i] > a[j]:
swap(a[i],a[j])
----
Also: A few years ago I emailed Prof. Richard Stanley of Enumerative Combinatorics fame asking whether it was related to any of the hundreds of problems in his Catalan Numbers list, and he said he didn't know a direct connection at the time (so maybe it's an addition to his list?):
> > permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left]
> Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423.
> Non-example: The permutation 3412 has four inversions (13), (14), (23) and (24), and the product (24)(23)(14)(13) is 4321 which is not the same as 3412.
> Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples).
And 14 is C_4, the fourth Catalan number.
OP's algorithm has both indexes going from 1 to n, and swapping when a[i] < a[j].
Yours is more efficient and easy to see why it's correct, but OP's is slightly simpler and more surprising.
Back in the 90’s for my high-school computer class, we were saving records on disk using TurboPascal and I was trying to sort my file in-place.
The sort was super slow, which I assumed was the disk head having to jump back and forth over larger distances of the array of records when comparing and swapping.
I reasoned if I could keep the compares and swaps between I and I+1, and then sweep those I’s forward, it’s the same number of overall compares but less head jumping with each compare/swap being adjacent records.
My implementation did speed things up quite a bit. I have no idea if my reasoning was right, or if I had some other inadvertent bottleneck. But I was proud of the speedier result.
I never explicitly pointed it out to the teacher, though, and didn’t get full marks on that homework because he said my overall program wasn’t user friendly enough.
// Given array a[1], ..., a[n]
for i = 1 to n - 1:
swapped = false
for j = i + 1 to n:
if a[i] > a[j]:
swapped = true
swap(a[i], a[j])
if swapped == false:
break
O((n-1)^2) = O(n^2).
As for time complexity, it changes from ϴ(n²) to O(n²). Alternatively, you can drop the O-notation and calculate precisely so as to include constant factor speedups, though your algorithm may end up slower in the worst case.
def swap(lst, a, b):
tmp = lst[a]
lst[a] = lst[b]
lst[b] = tmp
def optimized_sort(numbers):
i = 0
while i < len(numbers):
swapped = False
j = i + 1
while j < len(numbers):
if numbers[i] > numbers[j]:
swapped = True
swap(numbers, i, j)
if swapped == False:
break
j +=1
i+=1
return numbers
numbers = [1, 4,7,3,7,12,55,3,11,2,9,88,8]
optimized_sort([*numbers]) => [1, 4, 2, 7, 7, 12, 3, 3, 8, 9, 55, 11, 88]
(Whitespace dependent languages suck when it comes to passing around code snippets - it's just the honest truth)
Also I am pretty sure I saw this algorithm before. Doesn't it have a name?
But non-comparison algorithms [0] like radix sort [1] that rely on simplifying assumptions are not a joke and can be used in practice in many real-world cases.
[0] https://en.wikipedia.org/wiki/Sorting_algorithm#Non-comparis...
Which is an interesting topic in itself. Many times I have met people who said with absolute authority "no, it is not possible to implement this" only to be confronted with a counterexample. And that is because real life is rarely about spherical cows in vacuum.
I have once implemented a transactional, log-based database for credit card terminal (20MHz ARM, 2MB total unified memory).
The read (get value for key) operation was O(n^3) which the reviewers decided is "ABSOLUTELY FUCKING UNACCEPTABLE" (their words).
The fun started when I asked them to suggest better implementation. They could not come up with anything even remotely as fast.
And the basic reason was that n was guaranteed to be small as there wasn't even much space on the device for any more data. Other than that it exploited fantastic read ahead capability of the device plus it was so simple (basically couple nested loops) that CPU cache could be used very effectively.
I remember their O(nlog(n)) was never faster and actually about 50 times slower in most operations.
Nice job.
What it teaches people is to short cut the critical path of reasoning which is to first make sure you actually understand the problem and then the problem actually fits the assumptions. People are not taught that even a small divergence from assumptions can have dramatic difference on the actual solution or applicability of what they think is a solution. They are also not taught the actual assumptions or spot how they look. They talk about CS algorithms as if they worked on idealized computers, but then run them on real ones.
At school this is not taught because when it seems the problem fits the material it almost always is. People are actually rewarded for jumping to conclusions as this helps them go through material faster.
If you don't learn anything about the world you bring your learning with you and try to apply it to real world and that's how a lot of developers operate.
Especially in tech, you can usually look up solution to any problem easily. But for some reason this is the part everybody emphasizes rather than recognize knowing when to apply the solution is way more valuable.
I also think it is part of the wisdom behind "premature optimization is root of all evil".
If you fix w to a constant, then certainly one can claim that radix sort is O(n), but then so are comparison sorts as well.
That's not to say that radix sort isn't useful in practice, just because two sorting algorithms have the same asymptotic bounds doesn't mean they are equal, but it is to say that its performance is a matter of evaluating the constants rather than how it scales.
What you say only applies to sorting n unique/distinct keys. With no prohibition on duplicate keys, n & w vary quite independently. In this more general setting, radix sorting is indeed "really" O(nw) and w could be like 8 bits for some giant data set (EDIT and order is absolutely a useful property even with dups since there can be satellite data with the keys - also possibly bounded!). This is a common talking past each other problem in this area. To your credit you made this assumption explicit. (EDIT: "General purpose" may have some semantic unclarity, I suppose.)
In terms of relevance, everyone has their own, but my personal experience is that most (but not all) real world data allow both duplicate keys and bounding key width. In particular, the largest n data sets have been the least likely to have a prohibition on duplicate keys, and also the most likely to have small w (with a few exceptions). The random access pattern of memory writes in the passes of a radix sort may (or may not) be a problem, and constant factors matter, of course (as you also say). So tying w to n was has always seems a very special and somewhat artificial case to me.
I also have never heard of any practical O(n) comparison sort for fixed w before. Can you perhaps give a reference to some such algorithm? Thanks!
Pretty interesting implementation not actually sleeping tho.
while not is_sorted(a) do
shuffle(a)
But Bogosort isn't even the worst sorting algorithm out there! There is also Worstsort [2].
[1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
fn bogosort(a, comparator):
while not is_sorted(a, comparator) do
bogosort(a, rand)> There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n²) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.
This is not the Bubble Sort[0] as defined in Wikipedia. For one thing, it always has n^2 comparisons, is not always comparing adjacent elements, and does not terminate early.
[0] There are some who disagree and claim that it is.
I am in email conversation with someone who is claiming that it is just a more efficient version of the original Bubble Sort, and I'm trying to get the time to track down their references.
So:
I don't think it is Bubble Sort, I think it's clearly different, I have said so elsewhere, not everyone agrees.
It finds the largest number and places it at `i`. In the next iteration the largest number from 0 to `i` is placed at `i+1` Right up until `j` reaches `i`. Leaving a trail of orderliness.
As the value of `i` increases we approach and eventually equal ascending order.
What’s non-intuitive or what makes the comparison in the wrong order?
It’s much easier to explain if we just stop `j` at `i` each time.
I apologise.
Multiple comments elsewhere have been made by people who initially thought it was a Bubble Sort, and every other course and tutorial I know of starts with the Bubble Sort. So I admit to being surprised that you use this to teach algorithms. Personally, I find the algorithm given here completely unobvious, but perhaps that's just because I derived the Bubble Sort for myself back in the mid 70s, then read about O(n.log n) algorithms, and was hooked.
For me, this algorithm is very misleading, but if you find it a useful teaching tool then I've learned something, and I find it intriguing. I'd be interested to know if it's used in any other courses. Do you know of any?
snip description
> What’s non-intuitive or what makes the comparison in the wrong order?
It works, so obviously the comparison is right. But compare it with a classical Bubble Sort:
procedure bubbleSort(
A : list of sortable items
)
n := length(A)
repeat
swapped := false
for i := 1 to n-1 inclusive do
/* if these are out of order */
if A[i-1] > A[i] then
/* swap them and remember
something changed */
swap(A[i-1], A[i])
swapped := true
end if
end for
until not swapped
end procedure
if A[i] < A[j] then
...
And it's comparing every place with every other place, whereas Bubble Sort only ever compares adjacent items.
Being as familiar as I am with sorting algorithms in general, this, to me, feels unintuitive.
I guess my intuition doesn't match yours.
If you think about the point of all the adjacent comparisons in the inner loop for bubble sort is, it is finding the largest number and moving it to the last place in the array. It keeps doing that in a loop, the next time the second largest is found and at the second last place, etc.
This algorithm doesn’t particularly do anything different, it just finds the largest and places it at `i` instead of the last place in the array. You’ll find that as it does it’s thing the array from 0 to `i` is always in ascending order.
It’s very easy to teach this algorithm, the next variation that stops the inner loop at `i` instead of `n`, and the next variation that doesn’t do unnecessary swaps, which ends up being insertion sort I think? I would have to check.
This is immediately where my intuition for the correctness of this algorithm falls down. When `i` is 1 (in a 1-based array) this algorithm starts by putting the largest element in the 1st location.
Then it proceeds by putting the largest element in the 2nd location, then the 3rd, then the 4th, and so on, so I can see that the largest element ends up in the last place. What is harder to see is that in all the swapping about, it's guaranteed that the smallest ends up in the 1st location.
> * You’ll find that as it does it’s thing the array from 0 to `i` is always in ascending order.*
This requires (a) noticing that it's the invariant you want, and (b) showing that it's true. It feels like a lot more work than proving Bubble Sort works, and to me, it's a lot less "obvious" (for want of a better term). But in particular, you refer to "making steady, obvious progress." It's not obvious to me that in the mid-phases we are making progress. The largest element continues trudging upwards, yes, but it's not at all clear to me that what it leaves behind is ordered, and not chaotic.
I recognise that I'm not you, and I'm not in the same position as your students, but I still find this algorithm requiring a lot more work to understand than the Bubble Sort.
Is there any particular reason you use this algorithm as your starting point for teaching sorting?
(Copying from your sibling comment)
> It’s a lot more work to massage bubble sort into the other sorting algorithms they need to learn without scraping the code and starting from scratch.
An interesting observation. When I teach equivalent things I tend to present them separately and individually, so the students recognise that they are different in important ways, and then cross-connect them with transformations or other bridging techniques. Then they can see that they are different, but related.
I'll think about your approach next time I do something like this.
Meanwhile, if you would be willing to share a video of teaching this topic I'd be pleased to see it ... contact details are in my profile if you'd prefer direct contact, although I'm sure others would also be interested.
Do you have any (publicly-available) course materials that mention this algorithm? The OP mentions they were "unable to find any references to it", and I've been collecting references I find in this comment: https://news.ycombinator.com/item?id=28760986#28762275
> What’s non-intuitive or what makes the comparison in the wrong order?
In a sibling comment, 'ColinWright compares this algorithm to bubble sort, which has the comparison in the other direction. Another similar algorithm is this selection sort which differs by one character:
for i = 1 to n do
for j = i to n do
if A[i] < A[j] then
swap A[i] and A[j]
Well, for me what's non-intuitive is that if we started with a fairly-well ordered array:
[ 1, 2, 3, 5, 8, 4, 9 ]
The very first thing the algorithm would do would be to swap 1 and 2, even though they are already in the right order. The next thing it would do would be to swap 2 and 3, making it even worse. And so on, all the way down the line. It takes six swaps to put 1 finally back to where it belongs, and the rest of the array is hopelessly out of order.
It does work, yes, and you can eventually grok it, but I feel like you're not being honest to call this a completely intuitive algorithm to new CS students.
- It’s really simple
- It’s a bit counterintuitive, so makes a cute puzzle
- It’s a good exercise for a first correctness proof
- And it’s obviously a pretty pessimal algorithm, so students shouldn’t be tempted to use it in real code (hopefully...) Compared to bubble sort, which seems somewhat plausible, so people end up actually using it for real even though it’s a terrible algorithm.
Can you share with us your intuition as to why it works?
Is this a particularly complex algorithm or proof? No. But it reads like the author was terrified that someone would be able to understand their paper simply by reading it once and worried that would make the author look dumb. That's backwards, though. Easy to understand concepts are a good thing.
But of course they do get misused and there's not much more demoralizing than getting stuck on something 'obvious.'
The algorithm is not novel or in need of academic scrutiny. It's just a fun little sorting algorithm.
*: (or maybe it was my "Data Structures" professor, I don't remember which of those basic courses covered the basics of sorting algorithms)
Given the simplicity of this, obviously other people have found this algorithm before. But this might be the first publication mentioning it.
> It is difficult to imagine that this algorithm was not discovered before, but we are unable to find any references to it.
the author would almost certainly agree with your other points, and has some other interesting things to say in the article.
1. Allocation of new space is free, at least up to 2x the input size. 2. Moving a contiguous set of elements is as cheap as moving one element. 3. Moving an element, or set of elements, has a cost proportional to the distance moved.
To sort ~500 student tests by name, my favorite algorithm is
* Each person grabs a bunch of test. Split the test in 4 piles, using the first letter: A-F, G-L, M-Q, R-Z The same 4 piles for everyone. (I don't remember the exact borders. It may depend on your language. Perhaps 5 piles is better.)
* Each persons grabs a pile. Split each pile in subpiles by the first letter again. If some letter is too popular, split it using the second letter.
* Sort each small subpile, that has only 10-20 tests, probably using insert sort.
* Make a giant pile.
This can be classified as a combination of radix sort and insert sort. It's easy to parallelize to 5-10 persons.
If you later realize there are ~50 more test, just sort them using your favorite method and then use merge them, like in mergesort (or timsort?).
Though in that specific situation, the sufficiently smart and motivated could probably infer hand information.
https://stackoverflow.com/questions/69437526/what-is-this-od...
Those abominations could be tweaked throughout the development of the game, and along the way we'd sometimes "rediscover" a more common (sane) algorithm. The refinement in this paper reminded me a lot of that.
I'm pretty sure I used the double-loop technique to drive it, but mine wasn't quite as simple because I layered the joke by also using multiple XOR, instead of swap, to propagate the values through the array.
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]And it really, really isn't Bubble Sort. One of the defining features of Bubble Sort is that it only ever compares elements in adjacent locations. Others are claiming that if you optimise this then it becomes Bubble Sort, but someone else observes that if you "optimise" differently you end up with Insertion Sort.
That suggests that this is not Bubble Sort. It's something different that can be mutated into Bubble Sort, but it is, of itself, not Bubble Sort.
Only that the final link list (of index numbers) were in sorted order of which you then summarily write in the final array.
Which would have consumed some (n*(row-size)+n*(link-ptr-size+value-size) memory outside of its original array.
probably did O(n^1.5 for read operation which is WAY better than O(n^2) for bubble-sort.
Best in-its class algorithm for swap at O(2), worst case?
Delving into swap breakdown, its write operation might be O(3n+1) for writing a value then updating a link list pointer for each entry and for its link value into that final array; +1 for that NULL pointer at the end.
was arguably the lowest O (way back then) but at extremely high cost of memory. Never did learn which sort class did that variant falls into.
EDITED: insertion class, memory-hog-style.
One guy knocked down the time order considerably by doing tiny pre-bubblesort in blocks before entering into the link-insertion thereby making less passes over its million link-list chains: but only because he leveraged to fitting within its CPU L2/L3 cache. Professor said that the order got worse but not by huge logarithmic scale despite time speed-ups for completion.
Dang, the O order just got complicated for multi-level caches.
> It is difficult to imagine that this algorithm was not discovered before, but we are unable to find any references to it.
QuantumBogoSort a quantum sorting algorithm which can sort any list in O(1), using the "many worlds" interpretation of quantum mechanics. It works as follows: 1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway. 2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.) 3. All remaining universes contain lists which are sorted.
In fact, they’ll laugh at us for our first implementations of AI, which will look so stupid that they’ll call them BogoAI.
while (!IsSorted(array)) { }
https://en.m.wikipedia.org/wiki/Bubble_sort
This should be in the standard college level CS classes.
Edit:
As mentioned elsewhere, this is not exactly same as the textbook bubble sort
When I wrote this, I am saying in the sense that each outer iteration "bubbles" up to its correct place, by swapping.
Thinking twice this also appears to just be a selection sort, as it indeed swaps in each iteration the smallest element
But overall, the algorithm is not surprising at all to me. It seems unusual indeed though.
Consider, a Bubble Sort (as documented in TAoCP, for one) only ever compares elements in adjacent locations, whereas this routine compares every location to every other location.
if A[j] > A[i] then
It is true that i >= j, and sorted ascending values will have the property A[i] >= A[j].
It follows that swapping happens when the values are out of order, when
A[j] > A[i]Seen previously on HN https://news.ycombinator.com/item?id=2657277
Kind of a fun interview, but actually explores peoples knowledge.
void
cantbelievesort(int *p, size_t n)
{
int tmp;
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < n; j++) {
if (p[i] < p[j]) tmp = p[i], p[i] = p[j], p[j] = tmp;
}
}
}
4007cc: 31 c0 xor %eax,%eax
4007ce: eb 22 jmp 4007f2 <cantbelievesort+0x26>
4007d0: 8b 0c 87 mov (%rdi,%rax,4),%ecx
4007d3: 44 8b 04 97 mov (%rdi,%rdx,4),%r8d
4007d7: 44 39 c1 cmp %r8d,%ecx
4007da: 7d 07 jge 4007e3 <cantbelievesort+0x17>
4007dc: 44 89 04 87 mov %r8d,(%rdi,%rax,4)
4007e0: 89 0c 97 mov %ecx,(%rdi,%rdx,4)
4007e3: 48 ff c2 inc %rdx
4007e6: eb 02 jmp 4007ea <cantbelievesort+0x1e>
4007e8: 31 d2 xor %edx,%edx
4007ea: 48 39 f2 cmp %rsi,%rdx
4007ed: 75 e1 jne 4007d0 <cantbelievesort+0x4>
4007ef: 48 ff c0 inc %rax
4007f2: 48 39 f0 cmp %rsi,%rax
4007f5: 75 f1 jne 4007e8 <cantbelievesort+0x1c>
4007f7: c3 retq
void
dumbsort(int *p, size_t n)
{
int tmp;
for (size_t i = 1; i < n; i++) {
if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0;
}
}
4007f8: b8 01 00 00 00 mov $0x1,%eax
4007fd: eb 1e jmp 40081d <dumbsort+0x25>
4007ff: 4c 8d 04 87 lea (%rdi,%rax,4),%r8
400803: 48 8d 54 87 fc lea -0x4(%rdi,%rax,4),%rdx
400808: 41 8b 08 mov (%r8),%ecx
40080b: 44 8b 0a mov (%rdx),%r9d
40080e: 44 39 c9 cmp %r9d,%ecx
400811: 7d 07 jge 40081a <dumbsort+0x22>
400813: 45 89 08 mov %r9d,(%r8)
400816: 31 c0 xor %eax,%eax
400818: 89 0a mov %ecx,(%rdx)
40081a: 48 ff c0 inc %rax
40081d: 48 39 f0 cmp %rsi,%rax
400820: 72 dd jb 4007ff <dumbsort+0x7>
400822: c3 retq
Dumbsort is similar to gnome sort, but arguably somewhat simpler: whenever it finds an out-of-order pair, after reversing it, it throws up its hands and starts over (i = 0, xor %eax, %eax).
I don't think I invented it, but I can't remember who did. I'd be grateful for pointers.
If we treat looping up to n as one line of code, then both algorithms have the same count. And I think it's pretty fair to do that. Fortran, BASIC, APL, Perl, and so many others have syntax that's basically "for i = x to y". Let alone mathy languages that can loop over an array with a single character. Honestly, C is kind of weird for not having syntax for that.
For cyclomatic complexity, I don't know, setting i to 0 seems like cheating.
You definitely win on variable use.
Separate from the analysis, I have to wonder if there's a clever way to work in a saturating i-=2 instead of i=0. Then you can have N² efficiency without really changing the complexity.
In APL sorting the array P in ascending order is just
P[⍋P]
If we take Perl golf as our measure of "code complexity" you can't use a for-loop for dumbsort, because zeroing the ostensible loop counter doesn't reset the loop; there's a hidden loop counter you can't alter. You have to use an explicit while loop, which makes the cantbelievesort much simpler. Smalltalk and Python are the same way. But of course the shortest way to sort in all three languages is to invoke the built-in sort function: sort @p, p asSortedCollection, p.sort().
(You're right about FORTRAN and BASIC, though. You can futz with loop counters in those languages, just like in C.)
That's why I chose C and machine code as my metric. Smalltalk and Python maintain this hidden loop counter in the implementation, and also do garbage collection behind the scenes (which you might think was irrelevant, but the write barrier can significantly slow down heavily mutating algorithms like this one) and bounds checking. Numpy and APL additionally do implicit array broadcasting. All of these languages (except FORTRAN and BASIC) have built-in sort routines that are simpler to invoke than writing your own sort function. So I was looking for the language that would keep me as honest as possible.
But of course in a different machine language the answer might be different. For example, I haven't seen an instruction set with dedicated looping instructions that support nested loops, but make it inconvenient to clobber the loop counter in the middle of the loop, but it would be easy to design one, and there might be some advantage to doing so. (Code density, maybe, or unrolling iterations of the loop into a pipeline.) Then dumbsort would lose, because as in Python, it would have to be written as a regular while loop, which usually costs four instructions: an increment, a compare, a conditional jump, and an unconditional jump.
I think the i-=2 tweak you suggest converts dumbsort into gnomesort, which is just a sort of pessimized insertion sort. As your "saturating" comment suggests, gnomesort needs an additional operation to avoid running off the beginning of the array; some instruction sets do provide saturating arithmetic (it's often useful for DSP and graphics, even if it's not as often useful for indexing arrays), and many others provide a binary "max" operation (SSE's PMAXSW and friends, as well as, say, APL ⌈) which could convert an ordinary subtraction into a saturating subtraction.
> If we take Perl golf as our measure of "code complexity" you can't use a for-loop for dumbsort, because zeroing the ostensible loop counter doesn't reset the loop; there's a hidden loop counter you can't alter. You have to use an explicit while loop, which makes the cantbelievesort much simpler. Smalltalk and Python are the same way.
I think it can be reasonable to say that manipulating a loop counter is more complex than a strict loop over elements. Though you can get around that issue by using tail recursion for dumbsort instead of setting i to 0.
> But of course in a different machine language the answer might be different. For example, I haven't seen an instruction set with dedicated looping instructions that support nested loops, but make it inconvenient to clobber the loop counter in the middle of the loop, but it would be easy to design one, and there might be some advantage to doing so.
Maybe not nestable ones, but that's just a quirk of trying to have an especially compact instruction encoding. If the common case can be a single opcode like LOOP, or only a couple opcodes in a RISC architecture, I think it's reasonable to call it "one line of code".
> I think the i-=2 tweak you suggest converts dumbsort into gnomesort, which is just a sort of pessimized insertion sort. As your "saturating" comment suggests, gnomesort needs an additional operation to avoid running off the beginning of the array; some instruction sets do provide saturating arithmetic (it's often useful for DSP and graphics, even if it's not as often useful for indexing arrays), and many others provide a binary "max" operation (SSE's PMAXSW and friends, as well as, say, APL ⌈) which could convert an ordinary subtraction into a saturating subtraction.
Is there a way to write gnomesort that only has two simple conditionals? You're right that my suggestion brings it a lot closer to gnomesort, but I'm definitely not suggesting anything that checks if you're at zero.
void
dumbsort(int *p, size_t n)
{
dumbsort2(p, n, 1);
}
int
dumbsort2(int *p, size_t n, size_t i)
{
int tmp;
return i == n ? 0
: p[i] < p[i-1] ? (tmp = p[i],
p[i] = p[i-1],
p[i-1] = tmp,
dumbsort2(p, n, 1))
: dumbsort2(p, n, i+1);
}
The thing about the 8086 LOOP instruction is that it does expose the loop counter conveniently; it's just CX (or ECX on i386, RCX on amd64). So restarting it is just a MOV (not an XOR, because it counts down to 0).
Forth offers an instructive example of a set of operations (usually implemented in software rather than hardware) that support nested loops. Forth DO pushes both the loop counter and the upper bound on the "return stack" as what the ANSI standard calls a "do-sys"; there are words I, J, and K which get the innermost, second-innermost, and third-innermost loop counters, but cannot be used to set them. You can even save the contents of the return stack and restore it, but ANSI doesn't give you a way to restart the loop counter (which is certainly bad practice).
But that's just a matter of portability; any concrete Forth necessarily has to have a reliable way to set the loop counter so that LOOP can increment it. For CPUs, that circuitry wouldn't have to be accessible as an instruction, but general-purpose CPUs have a different concern: they need to have some way to save and restore all their architectural registers for preemptive context switching, which would include that loop counter — even if it wasn't exposed as a GPR like the i386 ECX. You could imagine providing that ability only via something like i386 PUSHAD, which would be a pretty inconvenient and slow way to restart the loop counter. But I'm not familiar with any instruction sets that work that way.
> Is there a way to write gnomesort that only has two simple conditionals? You're right that my suggestion brings it a lot closer to gnomesort, but I'm definitely not suggesting anything that checks if you're at zero.
I think that if you have a signed max() instruction that doesn't count as a conditional, this produces gnomesort with only two simple conditionals (untested):
void
browniesort(int *p, size_t n)
{
int tmp;
for (size_t i = 1; i < n; i++) {
if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = max(i-2, 0);
}
}
I think not counting max() as a conditional may be reasonable because, as I said, a number of CPU instruction sets provide it as a fundamental operation. At the hardware level it's no more conditional than the multiplexers used to read an operand from a source register in the register file.
I meant something more like this:
void
dumbsort(int *p, size_t n)
{
int tmp;
for (size_t i = 1; i < n; i++) {
if (p[i] < p[i-1]) {
tmp = p[i];
p[i] = p[i-1];
p[i-1] = tmp;
return dumbsort(p, n);
}
}
In the assembly version, you replace wiping eax with a jump.
It's kind of bogus that the 8086 loop-counter register CX isn't one of the index registers, isn't it?
for i: 0..n-1 A[i] = min(A[i:n])
// A function to implement bubble sort void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}As an approach to sorting, this is fairly complex - many simpler to understand solutions exist.
I still use it in a pinch, the delay is barely noticeable on today's hardware.
1. for j = 1..i-1, we're trying to "insert" a[i] into a[1..i-1]. Try simulating it yourself. I believe you will find out it's insertion sort.
2. for j = i..n, we're replacing a[i] with the smallest element among a[i..n].
Why it works: either (1) or (2) alone CAN DO THE SORTING. They do not conflict with each other.
Therefore, we can "optimize" this algorithm in at least two ways.
BTW, hope future powerful compilers can do this :)
> Letme re-interpret what the i-th iteration of the algorithm does:
> 1. for j = 1..i-1, we're trying to "insert" a[i] into a[1..i-1]. Try simulating it yourself. I believe you will find out it's insertion sort.
> 2. for j = i..n, we're replacing a[i] with the smallest element among a[i..n].
That is, they're saying in (2) that after an iteration of the outer loop, the ith value will be the smallest of all the values that succeed it in the sequence. This is demonstrably false. It is always the maximum value of the sequence itself, regardless of its initial position relative to i.
The following Python code is used to print out the result of running the inner loop on an arbitrary sequence but without altering the original value (so it won't actually be sorted at the end). The point is to demonstrate that the maximum value always ends in the ith position:
def inner(a, i):
for j in range(len(a)):
if a[i] < a[j]:
a[i], a[j] = a[j], a[i]
print(a)
def outer(a):
for i in range(len(a)):
inner(a.copy(), i)
a = [5,4,3,2,1,6]
outer(a)
[6, 4, 3, 2, 1, 5]
[4, 6, 3, 2, 1, 5]
[3, 4, 6, 2, 1, 5]
[2, 4, 3, 6, 1, 5]
[1, 4, 3, 2, 6, 5]
[5, 4, 3, 2, 1, 6]
[6, 4, 3, 2, 1, 5]
[4, 6, 3, 2, 1, 5]
[3, 4, 6, 2, 1, 5]
[2, 3, 4, 6, 1, 5]
[1, 2, 3, 4, 6, 5]
[1, 2, 3, 4, 5, 6]
[5, 4, 3, 2, 1, 6]
[4, 5, 3, 2, 1, 6]
[3, 4, 5, 2, 1, 6]
[2, 3, 4, 5, 1, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
Lazy bubble sort would still have a double loop counting to n, but it should be comparing A[j] and A[j+1]. 'i' would not be used inside the loop.
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]But apparently some people treated pixels as geometrical points without size?
If you don't know, you don't know.
It behaves more like insertion sort.
First of all, there's a Start button at the bottom of the right menu. Hit that and you will see that big color gradient sort itself.
However, that massive square is useless for seeing what's going on. So instead change the size to its lowest (8) and the delay to something like 400.
Now what you've got is 8 randomly-sorted columns. When you hit Start that algorithm will start sorting them each in parallel. You can just look at a single column and see the colors getting swapped. The darkest color moves to the top very quickly. This is a feature of how this particular algorithm works.
What's the point of the big square? Well, for one thing it's an interesting way to compare algorithms. Go back to the settings for a large number, a very low delay, and check off two other sorting algorithms, say Comb Sort and Heap sort. Hit Start and you'll see three very different approaches to sorting the columns.
for i = 1 to n do
- Inserts A[i] into A[1 to i-1], using the A[i]
- spot as a temp variable.
for j = 1 to i-1 do
if A[i] < A[j] then
swap A[i] and A[j]
- Does nothing.
for j = i do
if A[i] < A[j] then
swap A[i] and A[j]
- Permutes A[i to n], placing the maximum into
- A[i]. Since A[i] already has the max after the
- first iteration, it won't change, and we don't
- care how A[i+1 to n] is permuted since it gets
- sorted anyway.
for j = i+1 to n do
if A[i] < A[j] then
swap A[i] and A[j] - quick sort
- merge sort
- custom sort (this naive algorithm)
- bubble sort
And then you can clearly see the difference side by side, including the speed of the sort!
Quick sort is quick! Merge sort is better in the worst case but slower on this random data.
So if you visualize two sorts side by side, it's obvious which ones completes faster, and that corresponds to the algorithm's speed, right?
https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...
You can change the detail level slider while its running and see how it changes the animation. At level 1 (higher level) this and insertion are same.
* though, edflsafoiewq's analysis is nice and tidy
repeat n times:
for i = 1 to n-1:
if a[i] > a[i+1]:
swap(a[i], a[i+1])
Quite possibly, but the paper is seven pages long!
until sorted(A) {assign a random order to the elements of A}
There are n! ways to assign indices to the n items, so the expected time for the algorithm to complete grows at least as fast as n!, i.e. not ideal.
Bubble sort is the comparison of every pair.
If you compare only adjacent pairs, you eliminate an enormous number of redundant comparisons.
This is bubble sort without the redundancy elimination. It's just that the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm.
Bubble sort scans the full array repeatedly until finished, but only along the pairwise edge, and usually finishes way early
So in an array of 20 elements you have a maximum of 380 comparisons
This searches Euler's Little Triangle the whole way every time, so in an array of 20 elements, you have a maximum of 380 comparisons again
Seems similar, right?
Except doing pairwise you're likely to exit without doing all 19 scans - at the logarithm if it's well distributed - so it probably does either 4 or 5 scans, saving ~80% of the work
The issue isn't the ceiling; it's the common floor
Doing it the seemingly-normal way radically changes the common floor
So not only does this do different comparisons, it "radically" changes the number of "common floor" work.
And by the way, there's something wrong with your analysis of the number of scans needed for the 20 element bubble sort. I don't understand your argument, but I did some experiments with a randomly distributed array. I never saw it sort in fewer than 12 scans, after a few dozen trials.
I'm not sure what you mean here, but it seems like you're saying that bubble sort has every pair compared with every other pair, and that's not the case. A defining feature of Bubble Sort is that it only ever compares adjacent elements.
The sort presented here is definitely not Bubble Sort.
Now, it might be that you have more information than I have, and that would be interesting, but based on what you've said, I still think the algorithm presented here is genuinely not Bubble Sort.
You said:
> the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm.
Perhaps I should have emphasised the "is", and said:
>> A defining feature of Bubble Sort is that it only ever compares adjacent elements.
That might have served to emphasise that I had read your comment and was explicitly disagreeing with you. You claim otherwise ... perhaps I should have asked for an explicit reference from you to support your position, and provided for you the Wikipedia code to support mine.
In particular, on Wikipedia it says:
procedure bubbleSort(A : list of sortable items)
n := length(A)
repeat
swapped := false
for i := 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember
something changed */
swap(A[i-1], A[i])
swapped := true
end if
end for
until not swapped
end procedure
More, the algorithm in the linked paper appears at first glance to have the comparison the wrong way round. That's really different from the Bubble Sort that I know. It also explicitly performs n^2 comparisons, and Bubble Sort performs n-1 on each pass, and when it runs the full length every time, it performs (n-1)^2 comparisons at most. It really feels very different.
.
> So taking this as the definition
Random wikipedia code isn't a definition.
Have a nice day
Let's look at a few other sites:
"Bubble sort is a sorting algorithm that works by repeatedly stepping through lists that need to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order." -- https://www.techopedia.com/definition/3757/bubble-sort
"Bubble ... compares number X to the adjacent number Y." -- https://airfocus.com/glossary/what-is-bubble-sort/
"Bubble Sort ... works by repeatedly swapping the adjacent elements ..." -- https://www.geeksforgeeks.org/bubble-sort/
"... bubble sort works by comparing adjacent pairs of objects in the array." -- http://pkirs.utep.edu/cis3355/Tutorials/chapter9/tutorial9A/...
"Bubble sort ... each pair of adjacent elements is compared and the elements are swapped if they are not in order." -- https://www.tutorialspoint.com/data_structures_algorithms/bu...
"Bubble sort ... Compare the current number with the next number." -- https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/5
"Bubble sort ... compares two adjacent elements and swaps them until they are not in the intended order." -- https://www.programiz.com/dsa/bubble-sort
========
Added in edit:
Scans from TAoCP, Volume 3:
https://www.solipsys.co.uk/images/BubbleSort_a.png
https://www.solipsys.co.uk/images/BubbleSort_b.png
========
I'm really baffled by your claim. I've never seen anything other than the definition or implementation saying that it's adjacent elements being compared. Everywhere I've ever seen it's been a defining feature of the algorithm definition ... yet you claim otherwise.
Can you provide any explicit reference where the Bubble Sort is not explicitly comparing adjacent elements?
Notably, you're even providing scans from the TAoCP page I gave you, which have the relevant text carefully trimmed away, and are showing individual paragraphs whose text does not attempt to give a definition, despite that a definition is present on those pages
Who are you trying to convince, Frank? Nobody's reading this thread this late. Did you think I just didn't know what else was on the pages I gave you?
When an anti-vaxxer wants to make a point, they have to turn to hilariously inappropriate sources to pretend they're defended.
Techopedia, tutorials point, BBC news, a 2008 tutorial written by a student, and a random set of tutorials on a page full of broken links and misspellings. And very, very carefully edited Knuth.
Amusingly, one of them even explicitly spells out the same thing I did.
I see you're turning to the best in the business. And ignoring the coiner, again.
Good luck to you.
I'm providing scans of exactly the part where Knuth says the Bubble Sort only compares adjacent locations, just as I said.
You said:
> Bubble sort is the comparison of every pair.
This is contradicted by the scans of TAoCP that I've provided.
You said:
> If you compare only adjacent pairs, you eliminate an enormous number of redundant comparisons.
That's true, but you are eliminating redundant comparisons from something that is not a Bubble Sort.
> This is bubble sort without the redundancy elimination.
This is contradicted by the scanned excerpts from TAoCP.
> It's just that the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm.
The comparisons between locations that are not adjacent was never part of the Bubble Sort. You continue to claim otherwise, I have checked your references, as far as I can see they don't support your assertion. Please provide scans to support your claim.
Otherwise I bid you good day, and good health.
Seems a bit harsh.
With that so specific definitions, I could just get any other sorting algorithm and change it with different ways of comparing the elements to create "new" sorting algorithms.
The second loop runs from 1 to n, whereas in Bubble Sort it runs from 1 to n-1.
The comparison here is between A[i] and A[j], whereas in Bubble Sort it's always only between A[i] and A[i+1].
This one always performs n^2 comparisons, whereas Bubble Sort never performs n^2 comparisons.
This one compares elements to themselves, whereas Bubble Sort never compares and element with itself.
If you sort the array [1,2,3], the first thing this routine does is swap the 1 and 2, giving [2,1,3], whereas Bubble Sort runs along the array, makes no swaps, and exits.
This is not Bubble Sort.
It's true that if you take an existing sorting algorithm and change things around you can get other sorting algorithms. The question is then one of just how different it is.
If you choose to believe this is "just Bubble Sort" then that's up to you, but I disagree.
I never really had the intellectual talent or salesmanship for that, my gripe is that academia has this unsettling undercurrent of boasting and bluffing and backstabbing and it makes it just an unpleasant community in which to forge a livelihood.
Surely a healthy measure of these things has always existed, but the incentives has become perversely perverse and it really drives away people with a genuine aptitude and interest from areas where they can make genuine discoveries about nature and contribute to the sum of human knowledge.
And it drove me away too.
My job largely revolves around seeming important, not doing good work.
That happens in companies too. It's really strange. OTOH we also know that any objective measures will be gamed, which I guess is the same thing. Perceptions are more important than reality sometimes.
> From this we can see that XYZ. It is the author's opinion that ABC.