DEV Community

Cover image for Bubble sort
Pavel Ro
Pavel Ro

Posted on

Bubble sort

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
Enter fullscreen mode Exit fullscreen mode
  • 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.

Top comments (2)

Collapse
 
nancynieves profile image
NancyNieves

Why it is called bubble sort? Assam tantrik contact number

Collapse
 
edjin profile image
Edward Jin

Isn't the space complexity O(1)? Bubble Sort sorts the array in place.