Bubble sort

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

fun sort(arr: Array): Array {
var items = arr.copyOf()
for (i in 0 .. items.size - 1) {
for (j in i + 1 .. items.size - 1) {
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 - 1) {
sort(items)
}

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

println(milliseconds)
// about 2742 milliseconds