Shell Sort Algorithm in Ruby

1. Introduction

Shell sort, also known as the diminishing increment sort, is a generalization of the insertion sort algorithm that allows the exchange of elements that are far apart. The idea is to arrange the list of elements so that, starting from any given position, taking every hth element produces a sorted list. These lists are sorted individually, and the process is repeated for different values of h.

2. Implementation Steps

1. Choose an increment h to start with, where h is typically chosen as less than the total number of elements.

2. Sort the sublists created by considering elements at every hth interval.

3. Reduce the increment h and repeat step 2.

4. Continue this process until h is reduced to 1.

3. Implementation in Ruby Programming

def shell_sort(array)
  n = array.length
  # Start with a large gap and reduce the gap with each iteration
  gap = n / 2
  # Continue until the gap is 1
  while gap > 0
    # Do a gapped insertion sort for this gap size
    for i in gap...n
      temp = array[i]
      j = i
      # Shift elements by gap until correct position is found
      while j >= gap && array[j - gap] > temp
        array[j] = array[j - gap]
        j -= gap
      end
      array[j] = temp
    end
    gap /= 2  # Reduce the gap size
  end
end
# Client code
arr = [12, 34, 54, 2, 3]
puts "Original Array: #{arr}"
shell_sort(arr)
puts "Sorted Array: #{arr}"

Output:

Original Array: [12, 34, 54, 2, 3]
Sorted Array: [2, 3, 12, 34, 54]

Explanation:

1. Shell sort is an optimized version of insertion sort that sorts elements that are far apart from each other.

2. It begins with a large gap size and reduces the gap size in each iteration.

3. For each gap size, it performs a gapped insertion sort.

4. As the gap size reduces, the array becomes more sorted until the gap size becomes 1. At this point, the array is fully sorted.