Insertion Sort in Ruby

Overview

Insertion is a very simple and common sense approach to the sorting problem. It is stable, in-place, online, and efficient for small data sets and data sets that are already mostly sorted.

Concise

def insertion_sort(a)
  for i in 1...a.length
    k = a[i]
    j = i - 1
    while j >= 0 and a[j] > k
      a[j+1] = a[j]
      j = j - 1
    end
    a[j+1] = k
    p a
  end
  a
end

a = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
p a

s = insertion_sort(a)
p s
insertion_sort.rb

Verbose

# Insertion Sort for Ruby
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def insertion_sort(numbers)

  # Iterate through the length of the array,
  # beginning with the second element numbers[i]
  for i in 1...numbers.length
    key = numbers[i]
    j = i - 1

    # If element to left of key is larger then
    # move it one position over at a time.
    while j >= 0 and numbers[j] > key
      numbers[j+1] = numbers[j]
      j = j - 1
    end

    # Update key position.
    numbers[j+1] = key
    puts numbers.inspect
  end

  # Return sorted array.
  numbers
end

# Generate array of ten random integers.
unsorted = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
puts unsorted.inspect

# Sort.
sorted = insertion_sort(unsorted)
puts sorted.inspect
insertion_sort_verbose.rb

Sample Input and Output

$ ruby insertion_sort.rb
[7, 1, 2, 0, 6, 4, 5, 8, 3, 9]
[1, 7, 2, 0, 6, 4, 5, 8, 3, 9]
[1, 2, 7, 0, 6, 4, 5, 8, 3, 9]
[0, 1, 2, 7, 6, 4, 5, 8, 3, 9]
[0, 1, 2, 6, 7, 4, 5, 8, 3, 9]
[0, 1, 2, 4, 6, 7, 5, 8, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 3, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Further Reading