Conversation

Notices

1. clacke (clacke@social.heldscal.la)'s status on Thursday, 26-Oct-2017 22:53:38 EDT clacke
   Sorting Out Sorting, now in 2D!
   
   Pretty neat animations, and good explanations. No psychedelic 70s music though.
   
   https://m.imgur.com/t/art/GD5gi
   1. clacke (clacke@social.heldscal.la)'s status on Thursday, 26-Oct-2017 23:26:54 EDT clacke

      in reply to
      The description of Shell Sort is incorrect:
      
      > Shell sort is an improvement on insertion sort, instead of just looking at out-of-order neighbors, it starts out looking at a longer distance (half the list) for out of order elements, and insertion sorts them.
      
      There is no requirement on doing half the list. What gap sequence to be used is an open research problem, but nobody suggests factors of 2.
      
      https://en.wikipedia.org/wiki/Shellsort
      
      > Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive gaps are roughly equal to 2.2. This is why their sequence with ratio 2.2 and Tokuda's sequence with ratio 2.25 prove efficient. However, it is not known why this is so. Sedgewick recommends to use gaps that have low greatest common divisors or are pairwise coprime.
      
      The coprime one is what I learned two decades ago, probably from Sorting Out Sorting.
      1. clacke (clacke@social.heldscal.la)'s status on Thursday, 26-Oct-2017 23:35:11 EDT clacke

         in reply to
         And here's the grand piece, Sorting Out Sorting, itself:
         
         https://youtu.be/SJwEwA5gOkM
         
         > We have coded the algorithms as similarly as possible, in the C language, on a PDP-11/45 computer.
         1. clacke (clacke@social.heldscal.la)'s status on Thursday, 26-Oct-2017 23:55:02 EDT clacke

            in reply to
            Doesn't actually say anything about how to choose the sequence for Shell Sort. Huh.
      2. clacke (clacke@social.heldscal.la)'s status on Friday, 27-Oct-2017 00:03:27 EDT clacke

         in reply to
         > Nobody suggests factors of 2.
         
         Apart from Donald Shell himself, back in 1959, apparently! I stand corrected. Nobody since Frank & Lazarus, 1960. :-)
         
         http://wiki.c2.com/?ShellSort