Coding Journal

I don't understand this passage.  What are the two alternatives? ( Algorithms , 258) One way to implement shellsort would be, for each h, to use insertion sort indepen- dently on each of the h subsequences. Because the subsequences are independent, we can use an even simpler approach: when h-sorting the array, we insert each item among the previous items in its h-subsequence by exchanging it with those that have larger keys (moving them each one position to the right in the subsequence). Have to research different implementations of Shell Sort.  Would also help to clarify the mistake I made in my discussion yesterday. Having said that, I can think of two possibilities.  Given, for instance, h  of 3   and a sequence: 1 2 3 4 5 6 7 8 9 -- two methods would be first : Compare and exchange 1 and 4... ...2 and 5 ...3 and 6 ...4 and 7 ...5 and 8 ...6 and 9 -- or second : Do an insertion sort on 1, 4, and 7 Do an insertion sort on 2, 5, and 8 ...

Today I spent a little bit of time researching the "Shell" sort.  I wanted to post a few notes about the Princeton Algorithms Course's implementation to help me solidify my understanding. First, a little tidbit.  When I first heard about this algorithm, I thought it had something to do with shell games.  Turns out a man named Donald Shell discovered this method of sorting, whence the name. The Algorithms  book gives the following explanation (Sedgewick and Wayne,  Algorithms, 4th ed., p. 258): The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values o...