冒泡排序

// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass

func sort(_ arr: [Int]) -> [Int] {
    var items = arr
    for end in stride(from: items.count, to: 1, by: -1) {
        var swapped = false
        for j in 1 ..< end {
            if (items[j] < items[j - 1]) {
                let tmp = items[j]
                items[j] = items[j - 1]
                items[j - 1] = tmp
                swapped = true
            }
        }
        if (!swapped) {
            break
        }
    }
    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] = items.count - 1 - i
}
let count = 100
let start = Date()

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

let milliseconds = abs(start.timeIntervalSinceNow) * 1000

print(sortItems)
print("\(milliseconds) milliseconds")
// about 25 milliseconds