require 'date'
# Time Complexity O(n^2)
# Space Complexity O(1)
# neighbours change places until a pass makes no swaps:
# the largest element "bubbles up" to the end on every pass
def bubble_sort(data)
lst = data[0..-1]
lst.size.downto(2) do |last|
swapped = false
(1..last - 1).each do |j|
if lst[j] < lst[j - 1]
lst[j], lst[j - 1] = lst[j - 1], lst[j]
swapped = true
end
end
break unless swapped
end
return lst
end
items = [4, 1, 5, 3, 2]
sortItems = bubble_sort(items)
# sortItems is [1, 2, 3, 4, 5]
puts "items is #{items}"
puts "sortItems is #{sortItems}"
# *** simplified speed test ***
items = (0..200).to_a.reverse
count = 1000
start = DateTime.now
count.times{ |i|
bubble_sort(items)
}
delta = DateTime.now - start
milliseconds = (delta * 24 * 60 * 60 * 1000).to_i
puts "milliseconds is #{milliseconds}"
# about 1650 milliseconds