insertion sort Algorithm
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
However, insertion sort provides several advantages:
Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version
Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position
Stable; i.e., makes not change the relative order of components with equal keys
def insertion_sort(array)
0.upto(array.length - 1).each do |index|
element = array[index]
position = index
while element < array[position - 1] && position > 0
array[position] = array[position - 1]
array[position - 1] = element
position -= 1
end
end
array
end
puts "Enter a list of numbers seprated by space"
list = gets
insertion_sort(list)
print list
