BASICS | SORTING | INTERVIEW | BUBBLE SORT | BACKTOBASICS | INTERVIEW | CLEAN CODE | RUBY

By: Saurav

2018-04-10 03:35:00 UTC

We all have been there, done that. Well! This one is a refresher.

Bubble sort is all about bubbling the greatest element in each iteration. For sure we can do n iterations for array of size n but we can be more efficient by iterating till n-i in the i+1 round.

This is O(n^2) in Time complexity and O(1) in space

Few questions to ask before starting would be:
What's the size of the array
What's the element of the array? Float, Integer, Positive Negative, Characters etc?
Can an array be of only 1 or 0 elements?

let's write the tests and see the code:

p bubble_sort([1,2,5,3,7,10,8]) == [1,2,3,5,7,8,10]
p bubble_sort([-1,-2,4,3,2,10,-11]) == [-11, -2, -1, 2, 3, 4, 10]
p bubble_sort([1]) == [1]
p bubble_sort([]) == []


def bubble_sort(arr)
  return arr if arr.size < 2 
  size = arr.size 
  end_i = size 
  
  while end_i > 0 
    (0..end_i-2).each do |i|
      #p i 
      if arr[i] > arr[i+1]
        arr[i] = arr[i] - arr[i+1]
        arr[i+1] = arr[i] + arr[i+1]
        arr[i] = arr[i+1] - arr[i]
      end 
    end 
    end_i -= 1
  end
  
  
  return arr
end


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)