## DEV Community is a community of 620,623 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

# Insertion sort

Pavel Ro ・1 min read

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)