# 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
```

## 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
```

## 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]
```