Shell Sort

tags: shell-sort insertion-sort swap

Shell sort is an efficient algorithm that is based on insertion sort. Shell sort does not have large shifts like insertion sort.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def shell_sort(a)
  n = a.size
  h = 1
  
  # h is the increment factor
  while h < n/3  
    h= (3*h)+1
  end
    
  while h >= 1
    # insertion sort with inrement steps of "h"
    for i in (h..n-1)
      j = i

      while j>= h
        if a[j-h] > a[j]
          # swap
          a[j], a[j-h] = a[j-h], a[j]
        end
        j -= h
      end
    end
    
    h /= 3
  end
    
  return a
end

p shell_sort([5,1,0,4,9,2,8,3,6,7])