An Interest In:
Web News this Week
- March 19, 2024
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
- March 14, 2024
- March 13, 2024
April 19, 2021 07:01 pm GMT
Original Link: https://dev.to/buurzx/insertion-sort-45i2
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:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To