Array+sorting.swift

let xs = [3,5,1,4,6,3,9,11,1,0,3]
let ys = ["t","e","a","z","o","v","p"]

extension Array where Element: Comparable {
    func selectionSort() -> [Element] {
        guard self.count > 1 else {return self}
        var result = self
        
        for index in (0..<count - 1) {
            var indexLowest = index
            for forwardIndex in (index+1)..<result.count {
                if result[forwardIndex] < result[indexLowest] {
                    indexLowest = forwardIndex
                }
                if index != indexLowest {
                    result.swapAt(index, indexLowest)
                }
            }
        }
        return result
    }
}

xs.selectionSort()
ys.selectionSort()


extension Array where Element: Comparable {
    func insertationSort() -> [Element] {
        var result = self
        let count = self.count
        
        for sortedIndex in 1..<count {
            var backIndex = sortedIndex
            while backIndex > 0 && result[backIndex] < result[backIndex - 1] {
                result.swapAt(backIndex-1, backIndex)
                backIndex -= 1
            }
        }
        return result
    }
}

xs.insertationSort()
ys.insertationSort()

extension Array where Element: Comparable {
    func bubbleSort() -> [Element] {
        guard self.count > 1 else { return self }
        var result = self
        let count = self.count
        var isSwaped = false
        repeat {
            isSwaped = false
            for index in 1..<count {
                if result[index] < result[index-1] {
                    result.swapAt(index-1, index)
                    isSwaped = true
                }
            }
        } while isSwaped
        
        return result
    }
}
xs.bubbleSort()


extension Array where Element: Comparable {
    func mergeSort() -> [Element] {
        guard count > 1 else {return self}
        //divide
        let splitIndex = count/2
        let leftArray = Array(self[0..<splitIndex]).mergeSort()
        let rightArray = Array(self[splitIndex..<self.count]).mergeSort()
        //merge
        return merge(left:leftArray,right:rightArray)
    }
    
    func merge(left:[Element],right:[Element]) -> [Element]{
        var sorted = [Element]()
        var leftIndex = 0
        var rightIndex = 0
        
        while leftIndex < left.count && rightIndex < right.count {
            if left[leftIndex] < right[rightIndex] {
                sorted.append(left[leftIndex])
                leftIndex += 1
            }else if (left[leftIndex] > right[rightIndex]) {
                sorted.append(right[rightIndex])
                rightIndex += 1
            }else {
                sorted.append(left[leftIndex])
                leftIndex += 1
                sorted.append(right[rightIndex])
                rightIndex += 1
            }
        }
        if leftIndex < left.count {
            sorted.append(contentsOf: left[leftIndex..<left.count])
        }else if (rightIndex < right.count) {
            sorted.append(contentsOf: right[rightIndex..<right.count])
        }
        return sorted
    }
}

xs.mergeSort()
ys.mergeSort()

extension Array where Element: Comparable {
    func qsort() -> [Element] {
        guard self.count > 1 else {return self}
        let pivotIndex = self.count/2
        let pivot = self[pivotIndex]
        
        let less = filter{$0 < pivot}
        let equal = filter{$0 == pivot}
        let greater = filter{$0 > pivot}
        
        return less.qsort() + equal + greater.qsort()
    }
}

xs.qsort()
ys.qsort()