Insertion sort

Pavel Ro — Mon, 19 Apr 2021 19:01:15 +0000

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)

Bubble sort

Pavel Ro — Sun, 18 Apr 2021 19:17:13 +0000

Bubble sort is a sorting algorithm, which is commonly used in computer science. Bubble sort is based on the idea of repeatedly comparing pairs of adjacent elements and swap their positions if they exists in the wrong order.

Another words a bigger elements will 'bubble' towards the end and the smaller elements will 'bubble' towards the beginning until all elements are in the correct location.

Naive implementation:

def bubble_sort(array)
  return array if array.size <= 1

  swap = true

  while swap
    swap = false
    (array.length - 1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swap = true
      end
    end
  end
  array
end

method takes single array parameter.
return array if it's empty or consist of one element
swap is the variable (flag) to indicate whether or not swap occurred during a given pass of the array. Set initially to true
create a while loop that will run as long as swap is true
sets swap to false since immediately after the beginning of your loop there have been no swap
in the loop, iterates through array and if value of the element bigger than value of the next element, swapped them and set swap to true
the loop repeats until every item is in order and value of swap remains at false, the loop will terminated and return the sorted array.

Time Complexity: О(n^2)
Space Complexity: О(n)

PS. thanks Michelle for inspiring.

DEV Community: Pavel Ro

Insertion sort

Bubble sort