Learning Insertion Sort in Ruby

Solution 1:

You are overruning the bounds of your array. The example you were given was assuming 1-indexed arrays, but arrays in ruby are 0-indexed. The first line should be

for j in 1...num.length

Solution 2:

The other answer is correct that you are going past the end of the values in the array because it is 0-based but there are other changes you need to make to make the algorithm work:

for j in 1..(num.length - 1)

and

while i >= 0 and num[i] > key

Solution 3:

The simplest implementation is something like this:

def insertion_sort(arr)
  for i in (1...(arr.size))
    if arr[i-1] > arr[i]
      i.downto(1) do |el|
        if arr[el] < arr[el-1]
          arr[el-1], arr[el] = arr[el], arr[el-1]
        end
      end
    end
  end
  arr
end

arr = [5, 2, 4, 6, 1, 3]

p insertion(arr)

Note: to improve the efficiency of algorithm you can use the Binary search for elements comparison.

What Is Insertion Sort ?