The best analogy for insertion sort is a deck of cards. And you need to put them in the right order from smallest to greatest. You hold at least one card constant while you move the other cards around it to sort everything into order. The element that you considering could be moved one spot or over multiple spots.
def insertion_sort(array)
return array if array.size <= 1
(array.length).times do |i|
while i > 0
if array[i-1] > array[i]
array[i], array[i-1] = array[i-1], array[i]
else
break
end
i-=1
end
end
array
end
- return array if it's empty or include one element
- iterate through array with
(array.length).times
,i
represents the index of the array - in the loops when element's index > 0
- we set
if/else
condition and if previous value larger than current we swap them, else we terminate loops - if loops does not terminate we decrease index of array and continue
Time Complexity: О(n^2)
Space Complexity: О(n)
Top comments (0)