require 'date'

# Time Complexity O(n^2)
# Space Complexity O(1)
def bubble_sort(data)
    lst = data[0..-1]
    lst.size.times do |i|
        (i+1..lst.size - 1).each do |j|
            if lst[j] < lst[i]
                lst[j], lst[i] = lst[i], lst[j]
            end
        end
    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
items[5], items[6] = items[6], items[5]
count = 1000
start = DateTime.now

count.times{ |i|
    bubble_sort(items)
}

delta = DateTime.now - start
seconds = (delta * 24 * 60 * 60).to_f

puts "seconds is #{seconds}"
# about 0.795864 seconds