I think I saw something similar many years ago in a side competition of the national Math Olympiad were you can use computers. [spoiler alert] IIRC one student used a weird sorting algorithm, and after looking at it for a long time and testing, we called it a very inefficient insertion sort, and IIRC it was in the "wrong" direction. So my guess is that the student used this algorithm or something very similar.
They likely had at least one research assistant, proofreaders, etc. Maybe the author is attempting to distribute credit and lead the reader to infer there was just more than one person involved.
No. Many scientific papers are written in third person. "We" actually means "me or us the author(s) and you the reader who is following along and checking these details"
Or, yes. I worked as a research assistant gathering data for a professor at University who wrote 100s of papers in the area of graphics and computer vision.
It's intentional and normal. Academic papers traditionally write in plural form (regardless of co-authors) as it feels more inclusive towards the reader.
I've started using "the royal we" in my company's internal wiki so that hopefully readers won't think too hard about who the author was. In my case, I'm worried about new employees thinking, "Oh this is Jelly's page, I can't edit it."
Exactly, it’s less of a royal we and more of an inclusive / humbling we: I might be the author but I’m writing on behalf of and under the aegis of the group / organisation, so it’s our content not mine alone.
This is common in some fields. My understanding of it is that 'we' means 'the author(s) and the reader'. You'll sometimes see this voice changing when the author(s) give their own opinion. e.g.
> From this we can see that XYZ. It is the author's opinion that ABC.
Huh. I thought it was obvious: e.g., the top-left corner of the screen is (0, 0), the bottom-right corner is (640, 480), and pixels are 1x1 — we take the coordinate of their top-left corner to be their coordinate, so the top-left pixel has coordinates (0, 0), and the bottom-right one has (639, 479), and obviously the coordinates of their centres are (0.5, 0.5) and (639.5, 479.5).
But apparently some people treated pixels as geometrical points without size?
It's normal in signal processing to treat samples (whether audio or image) as points. A lot of things stop making sense if you replace them with line segments and rectangles.
Nearly all meaning the non-scientific computing ones, and particularly the ones with syntax inspired by C. Fortran, APL, Matlab, Wolfram, Mathematica, R, Julia, Cobol, Smalltalk and Lua are all 1-based, at least by default.
Welcoming open, thoughtful discussion and having people much smarter and with more experience than myself available to answer questions in which I'm not an expert is one of the main reasons I frequent HN.
At first it's entirely un-intuitive and obviously slow, but I kind of like the elegance, and the use of "<" makes sense once you realize that the final sweep will be with an i at the end of the array so that j will be ahead of it.
This looks interesting, but I can't get it to do anything. I see a purple gradient square, I see some widgets on the upper right. I see a box of code on the left. None of it seems to visualize a sort or even respond to input. What do I do?
It's a little confusing, but playing around with it I was able to understand it.
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.
Break the inner loop into three parts, j < i, j == i, j > i, and you can see it's insertion sort with extra steps.
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]
What you are seeing isn't speed but the iterations. If you see the source, I am drawing at certain location in the loop. Sometimes when swap happens, sometimes afterwards. More than speed you are seeing the steps.
Bubble sort only swaps adjacent pairs (thus "bubble", visualized the values "bubble up" to their correct spot) and is often abbreviated so that the inner loop runs on shorter segments (because the smallest or largest value, depending on how you write it, has been placed, no need to check that section again). this algorithm will swap non-adjacent pairs, making it more like insertion sort.
Viewing this as an "algorithm" may be why people find it to be surprising*. I don't find it terribly surprising, because I've played with a lot of sorting networks. Viewed as a sorting network, it's really clear how and why the algorithm works (and where it wastes half of its time).
* though, edflsafoiewq's analysis is nice and tidy
No, bubble sort uses a single index to compare items that are next to each other, and also has the condition reversed (> vs <), which is part of the surprise that this sort still has the correct increasing order.
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.
I did. Really, I did. I just happen to disagree with you.
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
So taking this as the definition, it explicitly only ever compares
adjacent elements of the array. And that's what I said. It might
be that it has derived from a version that does more comparisons,
and I'd be interested to see evidence for that, but this seems to
be the definition of what we call Bubble Sort.
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.
"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
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?
This is boring. I'm sorry you're unable to read my first comment, and keep requesting reference you've already recieved.
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.
I read your comment ... you are calling me a liar, and I don't appreciate that.
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.
This is getting more and more common in science, as a researcher's reputation and funding is more and more connected to their ability to get media/internet attention.
This comment made me weep internally. It's soul-crushing how relentless self-promotion is now as necessary good science for a "successful" academic career. (We can define that as getting paid anything at all by a university.)
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.
Oh yeah. I'm miserable. I have a 'dream career' but the reality of it is so unsettling. I work in a laboratory where collaboration only happens if it directly benefits someone's career in an "I'm famous" way... not an "I contributed to an important work" way. This is not unique. It's systemic.
My job largely revolves around seeming important, not doing good work.
>> 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.
Yeah, this doesn't have anything to do with academic "self-promoting", it's just a fun little paper on Arxiv. (If the author really wanted self-promotion, they should have used Twitter instead of that boring red site...) Don't really understand why people have issues with this one.
Assuming GP means General Purpose, yes, everyone who took an intro to algorithms should know that no sorting algorithm that relies on comparisons can do better than O(n*log(n)).
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.
That is why I specified "General Purpose". The moment you know something more about the data there might exist an opportunity to exploit that information to improve the algorithm.
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.
I think main reason is our flawed education. The tasks you are being given at school are usually constructed so that they fit the idealized knowledge you just learned.
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".
I once watched someone implement a heap in PHP in order to sort 4 domain names in order of priority and be able to resort them. The idea was I guess that at some point there may be 5 or even 6 of these and then we would really need the heap…
No general purpose sorting algorithm period can do better than O(n * log(n)), regardless of comparison or otherwise. For a radix sort with a complexity of O(n * w) where w is the key length, w converges to log(n) in the general case since the number of bits needed to represent n values grows logarithmically with n, hence you arrive back to O(n * log(n)). The O(n * log(n)) is an information theoretic result that applies even to radix sort, to be more precise the optimal sorting algorithm is Θ(n!).
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.
Maybe it has more to do with the actual distribution/form of the data? From my understanding radix sort can be incredibly fast when the numbers have fixed digits and evenly distributed in a predefined range (like phone numbers) but will be ineffective for floating point numbers or uneven distributions with extreme outliers.
> since the number of bits needed to represent n values grows logarithmically with n
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!
At some level, even comparing ‘a<b’ has a complexity related to the log of the magnitude of a and b. So if you’re doing a comparison sort over n unique values surely you’re going to run into a similar log n factor that the gp threw at the radix sort?
It depends how you count. There can be O(n log(n)^2) as you say, but I believe there are some comparison based algos where you only have to compare "fewer bits" to decide each comparison. So bit-wise cmps might still be O(n log n). However, you do have to move whole w-bit keys which is w bits wide. So, in full cost (cmp + space moves) unless you can do tricks to avoid the whole move, the comparison sorts do scale worse than radix-like digital sorts. And on general purpose CPUs people certainly compare batches of 8/16/32/64 bits at a time in HW. Personally, I think radix really does scale better, but maybe @Kranar can clarify his claim. (EDIT: there is often a random write pattern to digital sorts that can slow them down at massive scales, but that is definitely an {important} constant factor/different kind of "real machine" analysis.)
Shuffling is even less tricky if you're not trying to do it in place, if you're not trying to do it in linear(ithmic) time, or if you're not trying to induce a uniform distribution over all permutations (but rather just want some positive probability for all of them). Relaxing any combination of these conditions works just fine for Bogosort.
My gut says that combining that with other sort cycles in some magic ratio could do magical things. I'm quite wrong quite often ofc but the adventure is out there!
Fun fact: Fisher-Yates samples a uniform distribution over permutations and is therefor capable of producing any permutation, so you can sort any array in linear time using Fisher-Yates with its RNG replaced by a appropriate oracle. (So the complexity of sorting a array mostly reduces to the complexity of determining which permutation it's in relative to a sorted version.)
You can turn a sort into a shuffle by replacing the comparator with a random coin flip, and you already have defined a sort algorithm, so there's no added code complexity.
fn bogosort(a, comparator):
while not is_sorted(a, comparator) do
bogosort(a, rand)
You can't turn all sorts (not even all comparison sorts!) into a shuffle by replacing the comparator with a random coin flip. In fact your code post is a demonstration of that fact.
I turned in a similar algorithm for a college homework assignment, as a practical joke. (I'd been programming for 10 years already before I was able to go to college, so I was extremely bored in my first year Computer Science classes.)
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.
Yes, and the paper makes no mention of it, hm. Sorry to be a grumpy gatekeeper, but this really belongs as a blog post, not an arxiv paper, unless it were to cite more sources at least.
It now serves as a reference for this algorithm, something that was missing before and not well served by a blog post. It does not claim to have invented the algorithm.
I'd say both weird and coincidental :-). I'm the author of that StackOverflow question and have nothing to do with that paper. As far as I understand arXiv (I'm not familiar with it), the paper was submitted to arXiv before the StackOverflow answer that inspired my question, and published by arXiv after my StackOverflow question: https://arxiv.org/list/cs.DS/recent
> 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.
Do you really use this algorithm? Look more closely, if compares every element against every other element, and the comparison appears to be in the wrong order.
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.
There are others in this discussion who are claiming that it is Bubble Sort. Some have recanted, others are sticking to their guns.
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.
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
It's looking to see if A[i-1] > A[i], because then they are the wrong way round. Compare that with the code in this submission:
if A[i] < A[j] then
...
It's the other direction, which pulls me up short.
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 see now that people seem to be equating intuition with making steady, obvious progress.
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 algorithm ... finds the largest and places it at `i` instead of the last place in the array.
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?
The algorithm is essentially just inserting the i + 1 th element into the sorted subarray from 0 to i, and it inserts in the correct place. I’ll be teaching this next week or the one after, I’ll try to record a video and share if I remember. It’s harder to explain with just words.
I'd be fascinated to see this ... if you can do that I'd be grateful ... thank you.
(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.
Your original comment does not show that you are one of the few able to just read and understand a simple algorithm. Look around the many comments here where people misread this simple algorithm and readily jumps to premature conclusions. In that light I don't think you can say "there is an obvious intuition".
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.
Right. Isn't the intuition that the comparison and swap rule is applied to every possible combination? Put another way: How can you rearrange everything based on order and expect the net result to not be ordered at the end?
Hmm, come to think about it, it does have a lot going for it as an illustrative algorithm!
- 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.
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...
Yes, but you asked a computer science question with computer code instead of "pseudo code and arguments of correctness.", as Rafael kindly reminded you. :)
More like, GistNoesis used 0-based arrays and the paper uses 1-based arrays. “Arguments of correctness” sounds like Rafael basically told GistNoesis to answer themselves, which is of course a widely spread attitude on SE.
I think we should start recognizing more alternate information sources, such as blogs and stack exchange (i.e. attribute scientific credit and recognition to those posts).
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.
Wait a minute! What the hell is ‘automatic program search’? Is it like with Malbolge where the first working programs had to be written through brute-force search?
You define some test-unit cases, input-output pair.
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.
Is this really a new algorithm? I'm fairly sure my "Algorithms" professor* taught us this sorting algorithm twenty years ago. To be fair I don't think it was taught as a serious contender, not something to be implemented in production in the future, but instead as the baseline to measure the other algorithms, and also as teaching tool to introduce the fact that computers can't "instinctively look over" the whole set (like a human sorting a small set would do) but instead have to purposefully compare everything to everything.
*: (or maybe it was my "Data Structures" professor, I don't remember which of those basic courses covered the basics of sorting algorithms)
Pretty much everything you, I, or someone else is likely to come up with, someone else will have thought of before. That's why we usually attribute inventions and discoveries to the first people to bring to market or publish.
Given the simplicity of this, obviously other people have found this algorithm before. But this might be the first publication mentioning it.
I obviously wasn't in your class, but what your describing sounds more like the role 'bubble sort' plays in comp sci education. And while this looks similar to bubble sort it is very different in behavior.
I distinctively remember that bubble sort was presented later. We started with this naive double loop (and the naive simple sort as a sort into a different copy alternative) and incrementally added optimisations to reach the various named algorithms
"It is difficult to imagine that this algorithm was not discovered before, but we are unable to find any references to it." -- I've always maintained that for academics, if somebody hasn't written a paper for it, it doesn't exist. I can say I've seen this in actual code, in the wild, and I'm sure many others have.
It's more like, if it you can't find it, it doesn't exist. Seeing something published is probably the most common way for academics to "find" something, but if this algorithm was present in a lot of different code bases, made its way into the Linux kernel, etc., that would have been good enough, too.
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 is being likened to bubblesort in various places but your description (which I quite like) makes it seem like quicksort with an intentionally bad (worst possible?) bifurcation.
Well, it's not really dividing, sorting, and merging, so I wouldn't say it's too similar to quicksort.
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.
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.
I recall some kind of sort that requires a construction of link list for storing index numbers of the original array.
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.
Now I remember, it was a college try to improve the read operation of insertion-class sort algorithm.
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.
Not entirely unrelated, learning how merge sort worked and why it was more efficient than the naieve first guess of insertion sort was the light bulb moment in my understanding of computer science.
330 comments
[ 0.23 ms ] story [ 353 ms ] thread> From this we can see that XYZ. It is the author's opinion that ABC.
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.
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.
* though, edflsafoiewq's analysis is nice and tidy
edit: https://imgur.com/a/gXYE2Ru
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:
So taking this as the definition, it explicitly only ever compares adjacent elements of the array. And that's what I said. It might be that it has derived from a version that does more comparisons, and I'd be interested to see evidence for that, but this seems to be the definition of what we call Bubble Sort.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.
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.
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...
[1] https://en.wikipedia.org/wiki/Radix_sort
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.
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
[2]: https://arxiv.org/abs/1406.1077
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.
https://stackoverflow.com/questions/69437526/what-is-this-od...
> 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:
It's looking to see if A[i-1] > A[i], because then they are the wrong way round. Compare that with the code in this submission: It's the other direction, which pulls me up short.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:
This also sorts the array, but in the opposite order. It's true that seen in the correct light, both of these algorithms can be seen to work, but it definitely confuses people. For example, these three answers on Math Stack Exchange and Stack Overflow are incorrect about the sorting order: https://math.stackexchange.com/a/876452 https://stackoverflow.com/a/61970459 https://stackoverflow.com/a/57118286Well, 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?
> It is difficult to imagine that this algorithm was not discovered before, but we are unable to find any references to it.
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.
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.
*: (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.
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 ;) ?
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.