Sorts.swift

//: #Sort Algorithms - Page 65 Cracking the coding Interview E.4
//: If you have a better solution, please tell me! [email protected] - @JoanMolinas


//: ## BubbleSort
//: Start at the beginning of an array and swap the first two elements if the first is bigger than the second Go to the next pair, etc, continuously making sweeps of the array until sorted O(n^2)
var array:[Int] = [1,3,4,2,34,4,45,3,2,23,345,45]

func bubbleSort(array : [Int]) -> [Int]{
    let n = array.count
    var v : Int
    var copy = array
    
    for i in 0..<n {
        for j in 1..<(n-i) {
            if copy[j-1] > copy[j] {
                v = copy[j-1]
                copy[j-1] = copy[j]
                copy[j] = v
            }
        }
    }
    return copy
}

bubbleSort(array)

//: ## Selection Sort
//: Find the smallest element using a linear scan and move it to the front Then, find the second smallest and move it, again doing a linear scan Continue doing this until all the elements are in place O(n^2)

func selectionSort(var array : [Int]) -> [Int] {
    let n = array.count
    var index : Int!
    
    for i in 0..<n-1 {
        index = i
        for j in i+1..<n{
            if(array[j] < array[index]) { index = j }
        }
        swap(&array[i], &array[index])
    }
    
    return array
}
selectionSort(array)

//: ## Merge Sort
//: Sort each pair of elements. Then,sort every four elements by merging every two pairs. Then, sort every 8 elements, etc O(n log n) expected and worst case
//: IN CONSTRUCTION...


//: ## Quick Sort
//: Pick a random element and partition the array, such that all numbers that are less than it come before all elements that are greater than it Then do that for each half, then each quar- ter, etc O(n log n) expected, O(n^2) worst case
//: IN CONSTRUCTION...

//: ## Bucket Sort
//: Partition the array into a finite number of buckets, and then sort each bucket individually This gives a time of O(n + m), where n is the number of items and m is the number of distinct items
//: IN CONSTRUCTION...