6 comments

  • Someone17 minutes ago
    Paper about this with proof of how&#x2F;why it works: <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;2110.01111" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;2110.01111</a>, which says:<p>“There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(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.”*
  • amelius23 minutes ago
    I&#x27;d like to see a formal proof of this.<p>Not because I don&#x27;t believe it&#x27;s true, but because this might be a nice entry into formal proofs.
    • __s10 minutes ago
      <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;2110.01111" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;2110.01111</a>
  • edflsafoiewq13 minutes ago
    Previously (2021): <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=28758106">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=28758106</a>
  • logicallee19 minutes ago
    I&#x27;m pretty impressed by both Grok&#x27;s and Gemini&#x27;s static analysis of it. (I changed the name of the function to algo and asked them to figure out if it&#x27;s supposed to be a sort algorithm or a search algorithm. Both got it right.)[1] If someone else could please check the same prompt on ChatGPT and Claude (which I don&#x27;t have) please link.<p>[1]<p><a href="https:&#x2F;&#x2F;grok.com&#x2F;share&#x2F;c2hhcmQtMw_77a3a16f-642c-4ea7-95c7-28dd2b5cbec7" rel="nofollow">https:&#x2F;&#x2F;grok.com&#x2F;share&#x2F;c2hhcmQtMw_77a3a16f-642c-4ea7-95c7-28...</a><p>and<p><a href="https:&#x2F;&#x2F;share.gemini.google&#x2F;HADqPiEaeHQ9" rel="nofollow">https:&#x2F;&#x2F;share.gemini.google&#x2F;HADqPiEaeHQ9</a>
  • enjoyyourlife2 days ago
    Is this just bubble sort?
    • azertify43 minutes ago
      Matt Parker has an excellent video on this algorithm which should help illustrate why it&#x27;s absurd (and not bubble sort): <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=ixXOUeBOPJw" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=ixXOUeBOPJw</a>
    • Arainach39 minutes ago
      It&#x27;s not, but it&#x27;s conceptually very similar at first glance.<p>One important thing to note is that bubble sort places one element in the correct position each pass and then *stops looking at that position ever again*.<p>This algorithm looks at all N elements every pass.<p>Others have shared a bunch of great videos and writeups. Without reading them, my initial assumption is that this builds things bottom up (such that after the first pass, the element in position 0 is guaranteed to be the lowest element) and that despite it being compared again and again, it&#x27;s <i>essentially</i> placing one element each pass, but I could be wrong.
      • whizzter26 minutes ago
        Technically the first pass will ensure that the smallest element ends up at position 0 even if it&#x27;s looked at more times.<p>Bubblesort really is a family of &quot;this is something I figured out myself that runs by looping in O(N^2) by moving things to the front&#x2F;back&quot;
    • amelius23 minutes ago
      The hint is in the &quot;&lt;&quot; operator.
    • throwawayffffas7 minutes ago
      That was my first instinct as well. But if you look closer you will see, it&#x27;s actually insertion sort by someone who didn&#x27;t pay attention in class.<p>It misses the revelation you can skip already sorted positions when deiciding what goes in the next position.<p>Btw. Ofcourse it sorts, it&#x27;s basically insertion sort with extra swaps.
    • rcxdude43 minutes ago
      Look at it more carefully. Just reading the code, you&#x27;d think someone got confused between insertion sort and bubble sort and made a mashup that can&#x27;t possibly work. But it still does.
    • Muhammad5231 day ago
      No, it&#x27;s not. There&#x27;s a science paper with 3 theorems that prove it actually does sort
    • stavros35 minutes ago
      It took me a while, but the surprising part is that the inner loop goes back to the first element again, unlike bubble sort which never revisits the outer loop&#x27;s elements. So, at some point you&#x27;ll compare element 3 with element 1, and swap so that 3 is smaller than 1, which is surprising.
    • Jyaif42 minutes ago
      it&#x27;s bubble sort without the early return.<p>[edit: my bad, it&#x27;s not bubble sort]
      • rcxdude41 minutes ago
        Pull up the pseudocode for bubble sort and compare it.
        • Jyaif39 minutes ago
          indeed, it&#x27;s not bubble sort