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]