Insertion Sort Algorithm in Ruby

[5886 views]

What is Insertion Sort?

Insertion sort relies on the concept that one element from the input elements is consumed in every iteration to seek out its correct position i.e, the position to which it belongs in a sorted array.

In an Insertion sort, the first element in the array is considered as sorted. In an insertion sort, each element in the array is checked with the previous elements, which results in a growing sorted output array. With every iteration, the insertion sorting algorithm removes one element at a time and finds it's appropriate location within the sorted array and inserts it there in the sorted list. The iteration continues until the whole list is sorted.

For Insertion Algorithm, you can refer our previous post Algorithm for Insertion Sort

insertion_sort.rb

#insertion_sort.rb array = [] i = 0 #convert string array into integer array ARGV.each do |x| array[i] = x.to_i i = i + 1 end p "Input Array:" array.each do |x| p x end for i in 1..array.length-1 current = array[i] #set the current element j = i-1 #the element just to the left of current element index = i while current < array[j] && j >= 0 array[j+1] = array[j] index = j #save the position where the element will be inserted j = j-1 end array[index] = current end p "New Array:" array.each do |x| p x.to_i end