import java.util.Date

// Time Complexity O(n^2)
// Space Complexity O(1)

fun sort(arr: Array<Int>): Array<Int> {
    val items = arr.copyOf()
    for (i in items.indices) {
        for (j in i + 1..<items.size) {
            if (items[j] < items[i]) {
                val tmp = items[j]
                items[j] = items[i]
                items[i] = tmp
            }
        }
    }
    return items
}

var items = arrayOf(4, 1, 5, 3, 2)

val sortItems = sort(items)
// sortItems is {1, 2, 3, 4, 5}
sortItems.forEach { print("$it ") }
println()

// *** simplified speed test ***
items = Array(200) { 0 }
    .mapIndexed { i, _ -> i }
    .toTypedArray()
val tmp = items[5]
items[5] = items[6]
items[6] = tmp
val count = 10000
val start = Date()

for (i in 0..<count) {
    sort(items)
}

val milliseconds = Date().time - start.time

println(milliseconds)
// about 1306 milliseconds