Monthly Archives: February 2016

bubble sort ruby

Basically bubble sort will sort a collection by looping through a collection and checking if the current position array[i] value in the collection is greater than the next position array[i+1] in the collection.  We also set a swapped variable = false.  If the first value is greater than the next value, then we swap those values and set swapped variable to = true.


arr = [2,49, 400,25,4, 23, 1, 4,2, 3000, 42]

def bubble_sort(array)
length = array.length

loop do
swapped = false
(length -1).times do |i|
if array[i] > array[i+1]
array[i], array[i+1] = array[i+1], array[i]
swapped = true
end
end
break if !swapped
end
array
end
puts bubble_sort arr

In the inner loop if we swap a value, meaning the collection was not sorted, we set the swapped value to true.

Notice that I have a variable of swapped = false, so essentially we will continue to loop after the inner loop finishes unless the swapped value becomes false.  Then I can break out of my outer loop and return the array.

Bubble sort is a slow algorithm, bad at scaling.  If we increase our collection size by even a little it will dramatically increase our run time.  There is a relationship between the input size and run time.

The worst case scenario is when our collection is given in descending order.  This means we have to do the maximum number of swaps to sort it.  In the worst case if we have n amount of elements in the array, we have to perform ` cn2` where c is a constant even if n changes.  If every swap takes a constant amount of time, the run time of bubble sort will increase quadratically as input size increases.  This means bubble sort is O(n2), or run time scales quadratically.  

The amount of memory this sort takes can also be approximately measured using big O.  In this case we don’t allocate any additional memory so bubble sort’s space complexity is O(1) or constant.

Advertisements