This algorithm expands on concepts derived from Insertion Sort, and effectively uses those strategies by optimizing and consolidating swap operations per scan. Wikipedia offers some great background information for Shell Sort.

The example below is coded to the "poor" implementation of Shell Sort which operates in O(N²) time₁, and room for improvements exist by optimizing the gap sequence; N/2 is the gap strategy used here. An effective gap strategy can lend a O(N^3/2) down to O(N^4/3) runtime.

def shell_sort (list)
   gap = list.length/2
   while(gap > 0)
      list[gap..list.length-1].each_with_index do |element, index|
         j = (index += gap)
         index.step(gap-1, -gap) do |j|
            if ( j > 0 && j >= gap && element < list[j-gap] ) then
               list[j] = list[j-gap]
            else
               break
            end
         end
         list[j] = element
      end
      gap /= 2
   end
   list
end

Elements that are a "gap" apart, are compared and sorted; as the gap diminishes over each repitition, elements which are closest together are eventually compared.

Code Review
Start with a gap of N/2, and iterate until adjacent elements have been processed

def shell_sort (list)
   gap = list.length/2
      while(gap > 0)

Currently Ruby does not support an iterator which starts at a given index, so we will use the standard array API to obtain a sub-list which starts from "gap" and ends at the last element. We then iterate over that sub-list, and obtain each element and index.

list[gap..list.length-1].each_with_index do |element, index|

The sublist is returned as a seperate object, and therefore it's index starts at "0"; we must compensate for this by adjusting "index" to "index + gap". Additionally, we introduce "j" here so that we can use it outside of the upcoming loop; note, it's value at this point in the sequence is arbitrary and has no meaning.

j = (index += gap)

We then take advantage of Ruby's "step" construct for integers, to loop using a custom step sequence of "-gap", starting at "gap-1". As we scan down the list, we essentially compare and swap elements, in a similar fashion to Insertion Sort.

index.step(gap-1, -gap) do |j|
   if ( j > 0 && j >= gap && element < list[j-gap] ) then
      list[j] = list[j-gap]
   else
      break
   end
end
list[j] = element

I offer the same caveat as with the Insertion Sort tutorial; I attempted rubify the code, and therefore this implementation may not be as efficient as possible (e.g. use of "step" versus other loop tactics, the use of Ruby's sub-array functionality, having to re-adjust the index, etc..). However, I hope this provides some valuable insight into both Shell Sort and Ruby.

Ruby, which is progressively gaining popularity in the industry, has struck an interest with me, and I've decided to take up the task of learning the language. Although I was first introduced to Ruby back in 2002, I never took the time to really get to know it.

Fast forward 6yrs later, and I've decided to get serious about it, and what better way to learn than to get in there and code up some common algorithms. As I venture on this journey, I will document my experience in efforts to help out others who are learning as well.

For this first example, I've coded up the simple "Insertion Sort" algorithm. Please note that in my attempts to "rubify" the algorithm, it is highly likely I may not have written it efficiently.

def insertion_sort (list)
   list.each_with_index do |element, index|
      index.downto(0) do |j|
         if (j > 0 && element < list[j-1]) then
            list[j] = list[j-1]
         else
            list[j] = element
            break
         end
      end
   end
end

Insertion sort operates on the basis that elements are sorted progressively as the code scans the list, and therefore after each scan S, elements 0 through S-1 are assumed to be in order, and element S is moved towards the left until it is in order.

Code Walkthrough
The following lines uses the standard list iterator API to obtain both the element and it's index, starting at the beginning of the list.

list.each_with_index do |element, index|

The inner loop uses the "downto" construct to start at the current index (from the outer loop), and counts backward to "0". Note that "downto" does not alter the value of "index". This loop does the work of comparing and swaping the current element with it's predecessors, and will appropriately shift "greater" ones up the list.

index.downto(0) do |j|

The following code segment defines the comparison logic in order to shift the element down the list, by moving all "greater" elements up the list. Once an appropriate location has been determined, the current element is inserted back into the list.

if (j > 0 && element < list[j-1]) then
   list[j] = list[j-1]
else
   list[j] = element
   break
end

One very important point to note is that array boundaries are somewhat loose in Ruby, and therefore an index of "-1" is considered legitimate and will not produce an array/list access violation -- it would point to the last element in the list. Therefore, in the core logic presented above, we account for that by detecting when "j" is no longer greater than "0" in our conditional statement. Regardless, in order to properly implement "insertion sort", strict boundaries are needed.


Additionally, due to Ruby's OO nature, the code presented above will work with any list of classes that support the "<" comparison operator. With that being said, Ruby also makes it possible to have lists that contain a heterogeneous set of classes since there is a lack of type-safety -- this can be both an advantage or disadvantage depending on how you intend to use this algorithm. If you're using a mixed set of classes, you would have to ensure that there is some logical ordering defined within your classes to satisfy the comparison methods.


I hope this tutorial has been helpful!