require 'date'

# Time Complexity from O(n log(n)) to O(n^2)
# Space Complexity O(log(n))
def quick_sort(data)
    def sort(s_data, fst, lst)
        return if fst >= lst

        i, j = fst, lst
        x = s_data[(fst + lst) / 2]

        while i <= j
            while s_data[i] < x
                i += 1
            end
            while s_data[j] > x
                 j -= 1
            end
            if i <= j
                s_data[i], s_data[j] = s_data[j], s_data[i]
                i, j = i + 1, j - 1
            end
            sort(s_data, fst, j)
            sort(s_data, i, lst)
        end

        return s_data
    end

    return sort(data[0..-1], 0, data.size - 1)
end

items = [4, 1, 5, 3, 2]
sortItems = quick_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|
    quick_sort(items)
}

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

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