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

 1def insertion_sort(a)
 2  for i in 1...a.length
 3    k = a[i]
 4    j = i - 1
 5    while j >= 0 and a[j] > k
 6      a[j+1] = a[j]
 7      j = j - 1
 8    end
 9    a[j+1] = k
10    p a
11  end
12  a
13end
14
15a = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
16p a
17
18s = insertion_sort(a)
19p s

Verbose

 1# Insertion Sort
 2#
 3# Input: A sequence of numbers in any order
 4# Output: An ordered sequence from smallest number to largest
 5#
 6def insertion_sort(numbers)
 7
 8  # Iterate through the length of the array,
 9  # beginning with the second element numbers[i]
10  for i in 1...numbers.length
11    key = numbers[i]
12    j = i - 1
13
14    # If element to left of key is larger then
15    # move it one position over at a time
16    while j >= 0 and numbers[j] > key
17      numbers[j+1] = numbers[j]
18      j = j - 1
19    end
20
21    # Update key position
22    numbers[j+1] = key
23    puts numbers.inspect
24  end
25
26  # Return sorted array
27  numbers
28end
29
30# Generate array of ten random integers
31unsorted = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
32puts unsorted.inspect
33
34# Sort
35sorted = insertion_sort(unsorted)
36puts sorted.inspect

Sample Input & Output

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

Further Reading