Below is the updated code:

def insertion_sort(list)
  num = list.length
  for i in (0..(num-2))
    if list[i] > list[i 1] && i == 0
      list[i], list[i 1] = list[i 1], list[i]
      i =1
    elsif list[i] == list[i 1]
      i =1
    elsif list[i] > list[i 1] && i > 0
      len = (list[0..(i 1)].length)
      list2 = list[0..(i 1)]
      list = list - list2
      count = 0
      while count <= len 1
        if list2[len-1] < list2[len-2]
           list2[len-2],list2[len-1]= list2[len-1],list2[len-2] 
        elsif  list2[len-1] == list2[len-2]
          count =1
          len-=len
        else
         count =1
         len-=1 
        end
      end
       list = list2   list  
    end
  end
   list
end

p insertion_sort([2,1,4,8,7,3,100,99,8])
p insertion_sort([2,1,4,8,8,7,3,100,99])
p insertion_sort([3790,780,780,1,55])

Summary:

1. code works if two identical integers are right next to each other :[2,1,4,8,8,7,3,100,99] and the array size > 5.
2. if the two identical integer are at random positions: [2,1,4,8,7,3,100,99,8]. Below error would occur aaa.rb:4:in `>': comparison of Integer with nil failed (ArgumentError)

with Line 4 code being: if list[i] > list[i 1] && i == 0

To solve 1. I changed the while loop to "while count <= len 1", so when array size is smaller than 5 the code would work. But not when identical integers are at random positions.

Does anyone know how to solve this? Thanks in advance!

CodePudding user response：

Thanks for the clarification in the comments. I see the problem now.

In the swap algorithm here

elsif list[i] > list[i 1] && i > 0
  len = (list[0..(i 1)].length)
  list2 = list[0..(i 1)]
  list = list - list2
  count = 0
  while count <= len 1
    ...

you are trying to split the array in two. You get list2 which is the first half of the array and then try and get the second half by subtracting list2 from list.

The problem with using subtract here is that if you have duplicates it will remove them and make your lists too short.

In the example [3790,1,780,55,23,50,1111,60,50] you should have a 50 in the first array and a 50 in the second half.

But using subtract removes one of those 50.

When you add the two temporary lists back together you are now one element short (the missing 50) and you get an out of bounds error when you get to the end of the array and try and access this 9th element which no longer exists.

Instead of using subtract here simply use the same method you used to make list2.

list2 = list[0..(i 1)] # All elements in list from position 0 to i 1
list = list[(i 2)..-1] # All elements in list from position i 2 to end of list

Now list and list2 are just the original list split, and when you add them back together are the end they should be the same length

def insertion_sort(list)
  num = list.length
  for i in (0..(num-2))
    if list[i] > list[i 1] && i == 0
      list[i], list[i 1] = list[i 1], list[i]
      i =1
    elsif list[i] == list[i 1]
      i =1
    elsif list[i] > list[i 1] && i > 0
      len = (list[0..(i 1)].length)
      list2 = list[0..(i 1)]
      list = list[(i 2)..-1]
      count = 0
      while count <= len 1
        if list2[len-1] < list2[len-2]
           list2[len-2],list2[len-1]= list2[len-1],list2[len-2] 
        elsif  list2[len-1] == list2[len-2]
          count =1
          len-=len
        else
         count =1
         len-=1 
        end
      end
       list = list2   list  
    end
  end
   list
end

p insertion_sort([2,1,4,8,7,3,100,99,8])
p insertion_sort([2,1,4,8,8,7,3,100,99])
p insertion_sort([3790,780,780,1,55])