Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
April 19, 2021 07:01 pm GMT

Insertion sort

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  arrayend
  • 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)


Original Link: https://dev.to/buurzx/insertion-sort-45i2

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To