Learning Insertion Sort in Ruby

Question

I have just started the MIT Introduction to Algorithms course through the material posted online. Along with the course I have also decided to learn/enhance my Ruby skills by coding the algorithms in it.

I am on the first algorithm given, which is Insertion sort, and I have the following code typed up but I am getting this error when I run it:

insertionsort.rb:5:in `>': comparison of Fixnum with nil failed (ArgumentError)

def  insertionsort(num)
for j in 2..num.length
 key = num[j]
 i = j - 1
 while i > 0 and num[i] > key
  num[i+1] = num[i]
  i = i - 1
 end
 num[i+1] = key
end 
puts num
end

numbers = [23,34,46,87,12,1,66]

insertionsort(numbers)

I'm sure it is a fairly basic problem but I just can't grasp what it is at the moment. Any help or tips would be very much appreciated.

Answer 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

Answer 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

Answer 3

Just a minor complement to the other, excellent answers:

I think it is now generally accepted that 0-origin indexing has a number of practical and empirical advantages over 1-origin indexing. Experience suggests that it just "works better" and is less error-prone.

That's why a lot of programmers number things from zero, and astonish "normal" folks.