BubbleSort

BubbleSort.swift

/// from Data Structures & Algorithms in Swift book
/// bubble sort  worst（O(n^2), if array is already sorted, best is O(n)）
///
/// - Parameter array: target array
public func bubbleSort<Element>(_ array: inout [Element]) where Element: Comparable {
    guard array.count > 2 else { return }
    for end in (1..<array.count).reversed() {
        var swapped = false // optimize, if array is already sorted, do less useless work
        for current in 0..<end {
            if array[current] > array[current + 1] {
                array.swapAt(current, current + 1)
                swapped = true
            }
        }
        
        if !swapped {
            return
        }
    }
}

/// normal version
///
/// - Parameter arr: unsort array
/// - Returns: sorted array
@discardableResult
func bubleSort<T:Comparable>(arr: [T]) -> [T] {
    
    var temp = arr
    for _ in 0..<temp.count {
        for j in 1..<temp.count {
            if temp[j] < temp[j - 1] {
                // use tuple
                (temp[j], temp[j - 1]) = (temp[j - 1], temp[j])
                /*
                let tmp = temp[j - 1]
                temp[j - 1] = temp[j]
                temp[j] = tmp
                */
            }
        }
    }
    
    return temp
}