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

func sort(_ arr: [Int]) -> [Int] {
    var items = arr
    for i in 0 ..< items.count {
        for j in i + 1 ..< items.count {
            if (items[j] < items[i]) {
                let tmp = items[j]
                items[j] = items[i]
                items[i] = tmp
            }
        }
    }
    return items
}


var items = [ 4, 1, 5, 3, 2 ]

var sortItems = sort(items)
// sortItems is {1, 2, 3, 4, 5}
print(sortItems)

// *** simplified speed test ***
items = [Int](repeating: 0, count: 200)
for i in 0 ..< items.count {
    items[i] = i
}
let tmp = items[5]
items[5] = items[6]
items[6] = tmp
let count = 100
let start = Date()

for _ in 0 ..< count {
    sortItems = sort(items)
}

let seconds = abs(start.timeIntervalSinceNow)

print(sortItems)
print(seconds)
// about 2.32 seconds