Learning Insertion Sort in Ruby

Learning Insertion Sort in Ruby

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

Learning Insertion Sort in Ruby

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

Insertion sort in Ruby

In the C++ version you have (i = 1; i < length; i++). Which means, it will not run the last round where i = length. That would be out of the array.

In ruby, because you set the offset of the index to 1, the last round, you would have i = length. Hence source[length] is out of source, so returns nil.

1 > nil  # source[j-1] > source[j] when j = length
# ArgumentError: comparison of Fixnum with nil failed

Creating Insertion Sort in Ruby

The problem is that pull_position is not an element of array. (It's an index.) So array.delete(pull_position) returns nil, which is assigned to checked_value. checked_value < array... raises the exception, because nil does not have a method <.

Instead of array.delete(pull_position) I expect you want array.delete_at(pull_position), though that's not enough to fix the code.

The problem was easy to spot when I ran the code and got this exception:

NoMethodError: undefined method `<' for nil:NilClass
    from (irb):39:in `block in insertion_sort'
        ...

This is valuable information. It tells me the exception occurred when

while checked_value < array[insert_point - 1] and insert_point >= 0 do

was executed and that checked_value was equal to nil. So it was then just a matter of seeing where checked_value was last assigned a value (nil), and bingo!

implement shell sort by ruby

I referenced Shell Sort in here : Shell Sort - Wikepedia, and from that I have understood your algorithm is wrong. Iteration of gap sequence is alright, I mean you iterate only upto d/2 == 1.

But for a gap, let's say 2, you simply iterate from 0 to list.length-2 and swap every j and j+2 elements if list[j] is greater than list[j+2]. That isn't even a proper insertion sort, and Shell Sort requires Insertion sorts on gaps. Also Shell Sort requires that after you do an x gap sort, every xth element, starting from anywhere will be sorted (see the example run on the link and you can verify yourself).

A case where it can wrong in a 2 gap sort pass :

list = 5,4,3,2,1
j = 0 passed :
list = 3,4,5,2,1
j = 1 passed : 
list = 3,2,5,4,1
j = 2 passed
list = 3,2,1,4,5

After it completes, you can see that every 2nd element starting from 0 isn't in a sorted order. I suggest that you learn Insertion Sort first, then understand where and how it is used in Shell Sort, and try again, if you want to do it by yourself.

Anyway, I have written one (save it for later if you want) taking your method as a base, with a lot of comments. Hope you get the idea through this. Also tried to make the outputs clarify the how the algorithm works.

def shell_sort(list)
  d = list.length
  return -1 if d == 0

  # You select and iterate over your gap sequence here.
  until d/2 == 0 do
    d = d / 2

    # Now you pick up an index i, and make sure every dth element,
    # starting from i is sorted.
    # i = 0
    # while i < list.length do
    0.step(list.length) do |i|

      # Okay we picked up index i. Now it's just plain insertion sort.
      # Only difference is that we take elements with constant gap, 
      # rather than taking them up serially.
      # igap = i + d
      # while igap < list.length do
      (i+d).step(list.length-1, d) do |igap| 

         # Just like insertion sort, we take up the last most value.
         # So that we can shift values greater than list[igap] to its side,
         # and assign it to a proper position we find for it later.
         temp = list[igap]
         j = igap
         while j >= i do
           break if list[j] >= list[j - d]
           list[j] = list[j-d]
           j -= d
        end
        # Okay this is where it belongs.
        list[j] = temp

        #igap += d
      end

      # i += 1
    end
    puts "#{d} sort done, the list now : "
    puts list.inspect
   end
   list
end

list = [10,9,8,7,6,5,4,3,2,1]
puts "List before sort : "
puts list.inspect
shell_sort(list)
puts "Sorted list : "
puts list.inspect

How do I write a recursive insertion sort?

This:

arr[0, arr.size - 1]

returns a copy of part of arr and changes to that copy will not be reflected in arr. So, your recursive step does nothing useful and your method is equivalent to this:

def recursive_insert(arr)
  return arr if arr.size<=1
  i=arr.size-1
  while arr[i-1]>arr[i] and i>0
    arr[i],arr[i-1] = arr[i-1],arr[i]
    i-=1
  end
  arr
end

and that gets the 1 in the right place and that's all.

---

Related Topics