[HN Gopher] Is this the simplest (and most surprising) sorting a...
___________________________________________________________________
Is this the simplest (and most surprising) sorting algorithm?
Author : ColinWright
Score : 453 points
Date : 2021-10-05 11:49 UTC (11 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| CobrastanJorji wrote:
| This is fun but I do wish papers would stop using "obvious" or
| "not difficult" so frequently. This paper has five uses of
| "obvious," 3 uses of "clear" or "clearly," a "should not be
| difficult," a "what can possibly be simpler?," and a "It is
| difficult to imagine that this algorithm was not discovered
| before."
|
| 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.
| yupper32 wrote:
| You're going about it backwards. It's not that those phrases
| need to be removed from this paper, it's that this paper should
| have been a blog post.
|
| The algorithm is not novel or in need of academic scrutiny.
| It's just a fun little sorting algorithm.
| tgb wrote:
| Of the five "obvious" words, two of them are used to say that
| something is _not_ obvious and your last two examples are
| something entirely different. The uses here seem quite
| reasonable. But these words should be helpful, not insulting!
| If it 's not clear, as the author claims, then you've likely
| misunderstood something. No point pondering it for twenty
| minutes, better go back and reread the statement first.
|
| But of course they do get misused and there's not much more
| demoralizing than getting stuck on something 'obvious.'
| sytelus wrote:
| Plus I completely dislike the title. These kind of papers treat
| arxiv as if it is discussion group. It is not. It is paper
| repository for things that has been written with lot of care
| and thought.
| gotostatement wrote:
| so now academic papers are titled like clickbait? xD
| noobermin wrote:
| Interesting, but I'm amused by the writing style. I'm assuming it
| won't be submitted to a journal because the style reads like a
| blogpost.
| daneel_w wrote:
| Looks just like a slightly smarter insertion sorter, which is a
| slightly smarter exchange sorter, which is a slightly smarter
| bubble sorter. I don't see what's surprising about the approach.
| jacobmischka wrote:
| > There is nothing good about this algorithm.
|
| Seems a bit harsh.
| dilap wrote:
| High level description of why it sorts:
|
| 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.
| dvogel wrote:
| 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.
| dilap wrote:
| 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.
|
| 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.
| 6510 wrote:
| > https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxg
| BAZ...
|
| That is the most beautiful thing in CS I've ever seen.
| [deleted]
| breck wrote:
| This visualization tool is amazing.
|
| Is rain just the atmosphere running bubble sort ;) ?
| [deleted]
| GistNoesis wrote:
| I remember asking the question on a stack-overflow site in 2015.
|
| 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...
| aasasd wrote:
| 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?
| Cryptonic wrote:
| Maybe there gotta be a paper or it does not exist xD
| jvanderbot wrote:
| Write it down or it didn't happen. More directly, write down
| the result separate from the method or it won't be discovered
| by the right audience.
| somenewaccount1 wrote:
| Yes, but you asked a computer science question with computer
| code instead of "pseudo code and arguments of correctness.", as
| Rafael kindly reminded you. :)
| aasasd wrote:
| 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.
| civilized wrote:
| That comment was a bit of an eye-roller. The post is
| perfectly clear as it stands.
| liversage wrote:
| The original question contained a sizeable chunk of what
| looks like C#. It was then edited and made much clearer
| perhaps in a response to the comment.
| svat wrote:
| See the edit:
| https://cs.stackexchange.com/review/suggested-edits/26152
| gnramires wrote:
| 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.
| kragen wrote:
| The algorithm from the paper is indeed an astonishingly simple
| sorting algorithm, and it is indeed surprising that it works:
| 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; } }
| }
|
| That's 10 lines of code according to David A. Wheeler's
| 'SLOCCount,' though arguably 9 would be fairer. Its cyclomatic
| complexity is 3, with a deepest statement nesting level of 4, and
| it has 5 variables: three locals plus two arguments. It compiles
| to these 17 amd64 instructions, occupying 44 bytes of code,
| although I could probably shave off a third of that if I wrote it
| by hand: 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
|
| However, arguably, _this_ sort routine is _even simpler_. It may
| or may not be surprising that it works: 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; }
| }
|
| By the same metric, that's _only 8_ lines of code (also only 8 by
| my "fairer" metric), its cyclomatic complexity is _only 2_ , its
| deepest statement nesting level is _only 3_ , and it has _only 4_
| variables (the same two arguments, but two locals instead of
| three). It compiles to _only 15 amd64 instructions_ , occupying
| _only 43_ bytes: 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
|
| On every complexity metric that was ready to hand, dumbsort is
| simpler than cantbelievesort. Except computational complexity:
| dumbsort is O(N3) while cantbelievesort is only O(N2).
|
| 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.
| meesg wrote:
| Selection sort with extra swaps
| willvarfar wrote:
| It has a perverse beauty and will stick in my mind for a while :)
| [deleted]
| [deleted]
| ernopp wrote:
| No one repping the old drop sort. Just returns the first item of
| the list, which happens to be an ordered list. Simples.
| lettergram wrote:
| I've been using the same program for years (since 2015) for
| interviews, intentionally adding some issues and asking what the
| code does, how to fix the bug(s), what to name the function, what
| are some properties that are problematic, etc.
|
| Kind of a fun interview, but actually explores peoples knowledge.
| Apocryphon wrote:
| Watch out, whiteboarding interviews.
| ormei88 wrote:
| isn't that bubble sort?
| notriddle wrote:
| Not really. Bubble sort compares adjacent elements, while this
| compares every element with every other.
| JohnHaugeland wrote:
| Yes.
|
| 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.
| recursive wrote:
| Bubble sort will not make any changes to a sorted array. It's
| a similar number of comparisons. They're just different ones.
| JohnHaugeland wrote:
| It's a radically different number of comparisons
|
| 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
| recursive wrote:
| Thank you for making my point.
|
| 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.
| ColinWright wrote:
| > _Bubble sort is the comparison of every pair._
|
| 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.
| JohnHaugeland wrote:
| I wish you would read the rest of the comment. I clearly
| explain this.
| ColinWright wrote:
| 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.
| JohnHaugeland wrote:
| My original comment covers all of this.
|
| .
|
| > So taking this as the definition
|
| Random wikipedia code isn't a definition.
|
| Have a nice day
| ColinWright wrote:
| > Random wikipedia code isn't a definition.
|
| 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/T
| utorials/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?
| miloignis wrote:
| 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.
| mannykannot wrote:
| Is this the simplest sorting algorithm ever?
|
| Quite possibly, but the paper is seven pages long!
| troymc wrote:
| A simpler sorting algorithm might be:
|
| 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.
| iainmerrick wrote:
| Is that really simpler? Both "until sorted" and "assign a
| random order" look significantly more complex than this
| entire algorithm.
| NoGravitas wrote:
| This is commonly referred to as "bogosort", the archetype of
| the perversely bad algorithm.
| musicale wrote:
| Isn't this basically selection sort with extra (useless)
| iterations in the inner loop?
| phaedrus wrote:
| 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.
| jimmyed wrote:
| Why does the paper have the title of a clickbaitey BuzzFeed
| article?
| 6gvONxR4sf7o wrote:
| Because the whole paper is just a fun little note.
| cyber_kinetist wrote:
| 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.
| earthscienceman wrote:
| 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.
| Y_Y wrote:
| 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.
|
| And it drove me away too.
| EVa5I7bHFq9mnYK wrote:
| It always was this way. Source - PhD in physics, 1988.
| earthscienceman wrote:
| 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.
| phkahler wrote:
| >> 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.
| revolvingocelot wrote:
| So that those familiar with Betteridge's Law can just browse
| right on by
| bertman wrote:
| Having read the paper, Betteridge may actually not be true
| here :D
| SkeuomorphicBee wrote:
| 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)
| BoiledCabbage wrote:
| 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.
| chmod775 wrote:
| 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.
| andi999 wrote:
| The 'that's why..' part seems non sequitor to me.
| robotresearcher wrote:
| The article does not claim it is new. The introduction says:
|
| > 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.
| amelius wrote:
| If it contains an "if" statement then GPUs won't like it, and I
| wouldn't call it "simple".
| alex_smart wrote:
| The amount of people in this thread that can't read an intro to a
| paper is too damn high.
| fartingflamingo wrote:
| Reminds me of the remarkably little-known AlgoRythmics sorting
| dances [0].
|
| [0] https://www.youtube.com/user/AlgoRythmics/videos
| zeroimpl wrote:
| As an algorithm, this is simple (4 very basic lines of code).
|
| As an approach to sorting, this is fairly complex - many simpler
| to understand solutions exist.
| kevin_thibedeau wrote:
| It would make for a simple hardware implementation. More general
| than fixed size sorting networks. It if all happens in parallel
| you trade gate area for speed.
| shultays wrote:
| Imo does not approach the simplicity of sleep sort:
| https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
|
| Also I am pretty sure I saw this algorithm before. Doesn't it
| have a name?
| notriddle wrote:
| Sleep sort is heap sort. The heap is just built into your OS.
| lmilcin wrote:
| Sleep sort is meant as a joke. Obviously, everybody
| understands there exists no O(1) GP sorting algorithm.
| falcor84 wrote:
| 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.
|
| [0] https://en.wikipedia.org/wiki/Sorting_algorithm#Non-
| comparis...
|
| [1] https://en.wikipedia.org/wiki/Radix_sort
| lmilcin wrote:
| 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.
| bartvk wrote:
| Amazing story, thanks for sharing!
| jsight wrote:
| I'm consistently amazed at how willing people are to make
| assumptions about optimizations with problems that don't
| fit their assumptions.
|
| Nice job.
| lmilcin wrote:
| 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".
| IgorPartola wrote:
| 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...
| Kranar wrote:
| 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
| Th(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.
| cyber_kinetist wrote:
| 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.
| cb321 wrote:
| > 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!
| jameshart wrote:
| 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?
| air7 wrote:
| Actually, for any specific size of N, every algorithm is
| O(1)...
| fnord77 wrote:
| https://en.wikipedia.org/wiki/Insertion_sort ?
| kps wrote:
| If this doesn't have a name (I didn't see one in the paper), I
| propose "interview sort".
| sundarurfriend wrote:
| All sorts are interview sorts - that's the only context in
| which they come up, for most programmers.
| genewitch wrote:
| That's probably true, however didn't the default sort
| change between python2 and python3, as a newer, faster
| algorithm was found and implemented?
| faizshah wrote:
| I can't believe someone implemented that in jq:
| https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#j...
|
| Pretty interesting implementation not actually sleeping tho.
| antognini wrote:
| Bogosort is pretty simple, too. while not
| is_sorted(a) do shuffle(a)
|
| However the shuffle function hides a surprising amount of
| complexity. It is nontrivial to write a correct shuffle
| function. [1]
|
| 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
| j16sdiz wrote:
| a good (even) shuffle is not easy.
| [deleted]
| CaptainNegative wrote:
| 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.
| infinisil wrote:
| It would even suffice to just swap two random elements
| every iteration!
| innocenat wrote:
| I think most C++ implementation of bogosort use
| std::next_permutation
| 6510 wrote:
| 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!
| fbn79 wrote:
| Is it exchange sort?
| https://mathbits.com/MathBits/CompSci/Arrays/Exchange.htm
| pents90 wrote:
| It's not. The inner loop operates only from i+1 to n in
| exchange sort and the resulting swaps are very different.
| egwor wrote:
| I think that they should name it Beautiful Sort
| gamacodre wrote:
| Back in the 80's and 90's, working on consoles in very tight
| space constraints, there were times we'd go with a horribly
| inefficient implementation of something like sort, because we
| only needed to sort 8 things and the savings in bytes of code was
| more important than the savings in time from a "better"
| algorithm.
|
| 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.
| justicezyx wrote:
| This is bubble sort
|
| 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.
| ColinWright wrote:
| I suggest you read elsewhere in this discussion, where many
| people have claimed it is a Bubble Sort, and most have then
| changed their minds.
|
| 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.
| cratermoon wrote:
| I kind of like Sleep Sort
| https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
|
| Seen previously on HN
| https://news.ycombinator.com/item?id=2657277
| strangattractor wrote:
| It is simply an inefficient bubble sort. A bubble sort makes an
| improvement by not comparing values that are already sorted. Eons
| ago this example was a common way to introduce making algorithms
| more efficient. Naive Implementation -> Better Implementation.
|
| // 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]); }
| ColinWright wrote:
| If you read elsewhere in this discussion you will see many
| people giving reasons why this is not simply an inefficient
| Bubble Sort. You may disagree with them, as others do, but the
| situation seems rather more complicated than just saying "Oh,
| it's just a Bubble Sort."
| dahart wrote:
| No. Look again. The compare is opposite of bubble sort's.
| Xophmeister wrote:
| This weirdly/coincidentally [delete as appropriate] showed up as
| a StackOverflow "Hot" question today
|
| https://stackoverflow.com/questions/69437526/what-is-this-od...
| dtjc wrote:
| 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
| jonsen wrote:
| The graphics in the first answer gives a nice demonstration.
| bo1024 wrote:
| 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.
| robotresearcher wrote:
| 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.
| gus_massa wrote:
| 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.
| userbinator wrote:
| Likewise, I also think this algorithm has been "discovered"
| many times but those who did were probably not intending to.
| worik wrote:
| Ok, it is not bubble sort. It is worse.
| SamBam wrote:
| From the paper:
|
| > There is nothing good about this algorithm. It is slow - the
| algorithm obviously runs in Th(n2) 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.
| dhruvdh wrote:
| Well, I teach Algorithms, I think there is an obvious intuition
| as to why this works and I use this algorithm to introduce
| sorting.
| iainmerrick wrote:
| 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.
| cwoolfe wrote:
| 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?
| kilovoltaire wrote:
| Note that the comparison is backwards, so by that line of
| thinking it would sort in reverse (descending) order ...but
| it doesn't
| ColinWright wrote:
| 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.
| dhruvdh wrote:
| Yes. I can read.
|
| 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.
| ColinWright wrote:
| > _Yes. I can read._
|
| 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 _un_ obvious, 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 guess my intuition doesn't match yours.
| jonsen wrote:
| 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".
| areyousure wrote:
| > I use this algorithm to introduce sorting.
|
| 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]
|
| 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/57118286
| iainmerrick wrote:
| Who said it was bubble sort? It's clearly not.
| ColinWright wrote:
| 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.
| areyousure wrote:
| Some links to discussions and/or accidental discoveries of this
| algorithm:
|
| 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...
| areyousure wrote:
| Stack Overflow (2020, with incorrect answer):
| https://stackoverflow.com/questions/61970160/what-is-the-nam...
|
| 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
| svat wrote:
| Wow how did you find all these? Have you been keeping track all
| these years, or did you somehow search for and find this just
| now?
| areyousure wrote:
| All today. I have been trying to carefully craft searches on
| Google and Stack Overflow. I wish Google Code Search were
| still around, or that Github code search were better.
| areyousure wrote:
| Github (2014--2016): https://github.com/echavarria/edx-
| mit-600.1x/blob/master/W05... https://github.com/slgraff/edx-
| mitx-6.00.1x/blob/master/pset...
| https://github.com/mbh038/MITx600/blob/master/600.1x/Problem...
| https://github.com/demidovakatya/courses/blob/master/mitx/mi...
|
| 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_!
| limoce wrote:
| 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].
|
| 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 :)
| kilovoltaire wrote:
| I think you misread the code, the comparison is the opposite of
| what you might expect, so a[i] is always the _largest_ element,
| and it is not inserted into a[1..i-1]
| edflsafoiewq wrote:
| No, GP is correct. At the beginning of an outer loop
| iteration, a[1..i-1] is sorted with a[i-1] the maximum
| element. The inner loop inserts a[i] into a[1..i-1] so that
| at the _end_ of the iteration, a[1..i] is sorted with a[i]
| the max.
| Jtsummers wrote:
| No, GGP is incorrect. To be clear, they wrote:
|
| > 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 _i_ th 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 _i_ th 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]
|
| Note that 6 ends up in the _i_ th position after finishing
| the inner loop. If we let it sort (so remove _.copy()_ ),
| after each iteration the maximum value is, again, always at
| the _i_ th position: [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]
|
| GP _is_ correct that it 's basically insertion sort
| otherwise, (1). To illustrate, the behavior if you don't
| compare _every_ pair is the same as insertion sort:
| [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]
|
| This is done by stopping the inner loop once _j_ reaches
| _i_.
| asow92 wrote:
| "ICan'tBelieveItCanSort(A[1..n])" what an incredibly cheeky
| academic paper.. I love it.
| jakub_g wrote:
| HTML version of the PDF: https://www.arxiv-
| vanity.com/papers/2110.01111/
| [deleted]
| yodelshady wrote:
| Slightly OT, but it always slightly bugs me that sorting
| algorithms are taught *only* in the context of computers, which
| obey different physics to sorting things. Has anyone done work on
| sorting algorithms under different cost functions than just
| "minimise comparisons"? I'm thinking something like:
|
| 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.
| gus_massa wrote:
| Not exactly what you are asking for but ...
|
| 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?).
| tgb wrote:
| What's the optimal sorting algorithm for your Bridge hand?
| Sorting and holding 13 cards is tricky enough to make me
| wonder.
| thehappypm wrote:
| Yeah it's a little different because the human mind isn't
| procedural -- you can perceive multiple cards at once, at a
| fuzzy resolution. You look at a hand and see "okay an ace, 3
| face cards, some other cards" then scan to resolve. So an
| optimal algorithm needs to take that cognition into account.
| yodelshady wrote:
| That's the sort of thing I hand in mind, yes. Should probably
| write what I think I'm doing down.
|
| Though in that specific situation, the sufficiently smart and
| motivated could probably infer hand information.
| ansaso wrote:
| Is this a discovery!? I'm 100% sure I wrote when I first started
| programming and obsessively tried to get the shortest solutions
| on codewars.
| stagger87 wrote:
| Did someone refer to it as a discovery? In fact, from the
| introduction in the article.
|
| > It is difficult to imagine that this algorithm was not
| discovered before, but we are unable to find any references to
| it.
| NoGravitas wrote:
| I expect it's "commonly rediscovered because it's so simple;
| rarely published because it's so obviously bad".
| nazgulnarsil wrote:
| I had a similar experience in college. The assignment was to
| print out a tree structure with any given initialization values.
| The professor and everyone else in the class printed the tree top
| down, like tree diagrams in textbooks. This required a bunch of
| fiddly spacing considerations. I realized that printing it out
| left to right required far simpler spacing. I think the final
| code was less than 20 lines with the core logic being 7 lines.
| The professor was very surprised it worked.
| grumpopotamus wrote:
| http://wiki.c2.com/?QuantumBogoSort
|
| 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.
| laurent92 wrote:
| The next generation will laugh at us for our first
| implementations of various algorithms in quantum computers. It
| will look like what you describe.
|
| In fact, they'll laugh at us for our first implementations of
| AI, which will look so stupid that they'll call them BogoAI.
| egberts1 wrote:
| 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.
|
| EDITED: insertion class, memory-hog-style.
| victorbstan wrote:
| "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.
| professoretc wrote:
| 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.
| tu7001 wrote:
| Lenin Sort: guaranteed linear time, if element is not sorted, get
| rid of it! :-D
| smusamashah wrote:
| It behaves more like insertion sort
| https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...
| tester756 wrote:
| cosmic ray sort
|
| while (!IsSorted(array)) { }
| _448 wrote:
| Since when have academic/research paper titles become click-
| baity? :)
| beyondzero wrote:
| This is silly but sort of relevant.
|
| 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...
| thomasahle wrote:
| The observation that "random numbers can be sorted in linear
| time" is actually often useful in algorithm design. A typical
| application is storing a sorted list of hash values.
| TacticalCoder wrote:
| It's not silly. That's basically the "counting sort" and it
| definitely has uses.
| bjoli wrote:
| That brings up memories! I did the same thing. We had to sort a
| million integers in the range 0-1000 (exclusive range). I did a
| counting sort, and beat every other solution handily.
|
| 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.
| waterhouse wrote:
| The same fixnums!? Fixnums are distinct from bignums in that
| they're small enough to fit in a machine word and therefore
| _don 't_ need to be objects allocated in the heap... Was this
| an odd implementation wherein fixnums were put into the heap
| anyway?
| cassepipe wrote:
| I have also heard about it as radix sort :
| http://www.codercorner.com/RadixSortRevisited.htm
| [deleted]
| MrYellowP wrote:
| > but _sort_ of relevant
|
| 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!
| kragen wrote:
| That's not silly, that's the right way to solve that problem,
| unless y - x is large enough that you'd benefit from using one
| bit per number instead of one word. Well, usually calling
| qsort() would be fast enough, and less code.
| pocketgrok wrote:
| Isn't this usually taught right before sort algorithms? It's a
| simple lead-in to the topic and is great for reasoning about
| memory overhead.
| dd444fgdfg wrote:
| ha, I did exactly the same thing!
| tshaddox wrote:
| The "set of random unique numbers between x and y" part stands
| out so strongly that I would be shocked if the whole point
| wasn't to encourage a non-comparative sort.
| ttul wrote:
| Haha. Reminds me of a lab where we had to program a 6502 to
| play some sort of game, rendered on an oscilloscope. My genius
| friend stayed up all night writing code that rendered the snake
| by dynamically writing code, rather than the obvious approach
| of reading the "snake" coordinates and rendering those to the
| screen.
|
| 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.
| catwell wrote:
| This is a slightly simpler (because of unicity) version of
| bucket sort or counting sort.
| sli wrote:
| I remember seeing a (gag) variation of counting sort that
| just provided each element as an argument to `sleep`.
| lacker wrote:
| I feel like bubble sort is simpler. repeat n
| times: for i = 1 to n-1: if a[i] > a[i+1]:
| swap(a[i], a[i+1])
|
| It's true you have to add and subtract 1, but you only have one
| variable, and of course the rationale for why it works is far
| simpler.
| xtat wrote:
| So academic papers have also gone the route of clickbait titles
| :)
| theli0nheart wrote:
| Does it bother anyone else that the paper has a single author and
| yet throughout they refer to themselves as "we"?
| dimitrios1 wrote:
| 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.
| klyrs wrote:
| 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"
| Foxboron wrote:
| It's intentional and normal. Academic papers traditionally
| write in plural form (regardless of co-authors) as it feels
| more inclusive towards the reader.
| OscarCunningham wrote:
| 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.
| crote wrote:
| The author neglected to mentioned F. D. C. Willard as co-
| author, obviously.
| NoGravitas wrote:
| Or Galadriel Mirkwood.
| tobr wrote:
| Just speaking for ourselves, it doesn't bother us.
| [deleted]
| ReactiveJelly wrote:
| 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."
| masklinn wrote:
| 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.
| bingohbangoh wrote:
| 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.
| paulcnichols wrote:
| A+ click bait paper title.
| svat wrote:
| [Edit: I took a quick glance at the paper and got carried away;
| the rest of this comment is about a different algorithm
| apparently known as "exchange sort", and an interesting property
| of it. The algorithm in the paper is actually different, and
| indeed more surprising.]
|
| 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])
|
| > It looks like bubble sort, but is closer to selection sort. It
| is easy to see why it works: in each iteration of the outer loop,
| `a[i]` is set to be the smallest element of `a[i...n]`.
|
| ----
|
| 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.
| keskadale wrote:
| INOI 2004. this guy's OG.
| goodcanadian wrote:
| Your algorithm is in the paper as a comparison, and it is
| described as a standard exchange sort.
| maxk42 wrote:
| Because I have a need to optimize: // 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
|
| This should reduce time complexity to O( (n - 1)^2 ) and stop
| sorting after the remainder of the array is sorted and tested
| one time.
| labawi wrote:
| I see where you're going, but your implementation broke the
| sort.
|
| As for time complexity, it changes from [?](n2) to O(n2).
| 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.
| y4mi wrote:
| it doesnt work though 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]
|
| removing the break gets you the correct order: [1, 2, 3, 3,
| 4, 7, 7, 8, 9, 11, 12, 55, 88]
| labawi wrote:
| Original code would be correct, if not for a few spaces -
| probably a typo.
| munk-a wrote:
| This is why I like me some curly braces.
|
| (Whitespace dependent languages suck when it comes to
| passing around code snippets - it's just the honest
| truth)
| [deleted]
| maxk42 wrote:
| It was just an indentation typo. Swap check should be one
| level higher.
| q-big wrote:
| > This should reduce time complexity to O( (n - 1)^2 )
|
| O((n-1)^2) = O(n^2).
| jeffwass wrote:
| I actually did the opposite! I was taught this sort in high
| school (I think the teacher called it shuttle interchange?),
| and I independently came up with the bubble sort on my own as a
| more-efficient in-place implementation on disk.
|
| 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.
| otto2 wrote:
| Back in time I was sorting records on disk using Atari ST and
| (probably) Omikron BASIC. I applied RADIX sort (or a variant)
| that I saw in one magazine. It worked as a charm on RAM disk,
| but once when I tried it on a floppy disk, it just took
| forever.
| BoppreH wrote:
| Not quite, your algorithm has j going from i+1 to n, and
| swapping when a[i] > a[j].
|
| 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.
| svat wrote:
| Oh yes, good point: I got carried away; there _is_ a
| difference! Simplicity is subjective (I think mine is simpler
| of course :P), but the algorithm in the post is indeed more
| surprising.
| pricecomstock wrote:
| Your algorithm does appear in Section 3.1 of the linked
| paper by the name "Exchange Sort"
| maltalex wrote:
| tl;dr the algorithm (the array is 1-based): for i
| = 1 to n do for j = 1 to n do if A[i] < A[j]
| then swap A[i] and A[j]
| SketchySeaBeast wrote:
| 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.
| hwers wrote:
| what does 1-based mean?
| calebegg wrote:
| The first element of the array is A[1], rather than A[0] like
| it would be in nearly all programming languages.
| goatlover wrote:
| 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.
| Scarblac wrote:
| Or maybe not so much inspired by C, but inspired by
| similar arguments as Dijkstra makes in his "Why numbering
| should start at zero": https://www.cs.utexas.edu/users/EW
| D/transcriptions/EWD08xx/E....
| dredmorbius wrote:
| There is of course the compromise position of 0.5.
| Scarblac wrote:
| Why compromise? Just have a helpful variable like Perl's
| $[ to set the first element index.
| tom_ wrote:
| I prefer 9. It makes no less sense than 1, but it is
| conveniently much closer to the + and - keys.
| notriddle wrote:
| My 0 key is twice as big as the rest of the digits.
| DougBTX wrote:
| https://www.realtimerendering.com/blog/the-center-of-the-
| pix...
| Joker_vD wrote:
| 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?
| foxfluff wrote:
| 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.
| goohle wrote:
| Which is rounded down to 0 or up to 1 at random.
| red_trumpet wrote:
| It's entries are A[1], A[2],...,A[n] instead of A[0],
| A[1],...,A[n-1].
| jimmyed wrote:
| It means you probably shouldn't be on Hackernews
| findalex wrote:
| > too young to know FORTRAN.
|
| If you don't know, you don't know.
| castis wrote:
| It means they should definitely be on HN where they're very
| likely to learn new things.
| ZeroCool2u wrote:
| 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.
| fullstop wrote:
| The array indexes start at 1, not 0.
| [deleted]
| [deleted]
| demosito666 wrote:
| aka bubble sort
| miloignis wrote:
| It is definitely not bubble sort, which only uses a single
| index comparing items next to each other in the array.
| [deleted]
| balefrost wrote:
| Check the direction of the comparison, and check the bounds
| of the loops. It's not really bubble sort.
| recursive wrote:
| And check whether the compared elements are adjacent.
| smusamashah wrote:
| This is how it looks like
| https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ...
|
| It behaves more like insertion sort.
| recursive wrote:
| 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?
| smusamashah wrote:
| Click Start at the bottom of control panel on right.
| SamBam wrote:
| 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.
| Izkata wrote:
| And if you start the inner loop at "j=i" and flip the
| comparison order, it turns into something very similar to a
| very slow selection sort.
| chubot wrote:
| Wow this page is very cool! I recommend clicking these four
| boxes: - quick sort - merge sort
| - custom sort (this naive algorithm) - bubble sort
|
| Then click "start".
|
| 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.
| smusamashah wrote:
| 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.
| chubot wrote:
| I think that is what I mean -- when there are fewer steps
| in the sort, then the visualization completes faster.
|
| 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?
| smusamashah wrote:
| Each draw step is one draw call. For example in some
| algos where there isn't a clear swap operation I draw the
| whole array in one step, which may or may not reflect all
| operations that happened before that draw call.
|
| https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxg
| BAZ...
|
| 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.
| edflsafoiewq wrote:
| 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]
| ColinWright wrote:
| Is the "Parallel Merge Sort" working? It doesn't seem to be
| doing anything ...
| klyrs wrote:
| 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
|
| edit: https://imgur.com/a/gXYE2Ru
| sunnyque wrote:
| for almost two decades I thought this is a bubble sorting
| algorithm
| Jtsummers wrote:
| 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.
___________________________________________________________________
(page generated 2021-10-05 23:00 UTC)