//: Playground - noun: a place where people can play

import UIKit

var str = "Hello, playground"

/// sum

func sum(array: Array<Int>) -> Int {
    if array.count == 0 {
        return 0;
    }
    
    var arrayM = array
    let first = arrayM.removeFirst()

    return first + sum(array: arrayM)
}

let total = sum(array: [2, 4, 6, 8])

/// count

func findTotalCount(array: Array<Int>) -> Int {
    if array.count == 1 {
        return 1;
    }
    
    var count: Int = 0
    
    var arrayM = array
    arrayM.removeFirst()
    count += 1
    
    return count + findTotalCount(array: arrayM)
}

let totalCount = findTotalCount(array: [2, 4, 6, 8])

/// maximum

func findMaximum(array: Array<Int>, max: Int) -> Int {
    if array.count == 0 {
        return max;
    }
    
    var arrayM = array
    var m = max
    
    let first = arrayM.removeFirst()
    m = first > max ? first : max

    return findMaximum(array: arrayM, max: m)
}

let max = findMaximum(array: [2, 4, 6, 8, 3], max: 0)

/// quick sort

func quickSort(array: Array<Int>) -> Array<Int> {
    if array.count < 2 {
        return array
    }
    
    let pivot = array[0]
    
    var leftArray = Array<Int>()
    var rightArray = Array<Int>()
    
    for i in 1...array.count - 1 {
        let item = array[i]
        if item <= pivot {
            leftArray.append(item)
        } else {
            rightArray.append(item)
        }
    }
    
    var result = Array<Int>()
    result.append(contentsOf: quickSort(array: leftArray))
    result.append(pivot)
    result.append(contentsOf: quickSort(array: rightArray))
    return result
}

let qs = quickSort(array: [5, 2, 7, 10, 30, 200, 156])

/// quick sort in best-case

func quickSortInBestCase(array: Array<Int>) -> Array<Int> {
    if array.count < 2 {
        return array
    }
    
    let middleIndex = array.count / 2
    let pivot = array[middleIndex]
    
    var leftArray = Array<Int>()
    var rightArray = Array<Int>()
    
    for i in 0...array.count - 1 {
        let item = array[i]
        if item < pivot {
            leftArray.append(item)
        } else if item > pivot {
            rightArray.append(item)
        }
    }
    
    var result = Array<Int>()
    result.append(contentsOf: quickSort(array: leftArray))
    result.append(pivot)
    result.append(contentsOf: quickSort(array: rightArray))
    return result
}

let qsInBestCase = quickSortInBestCase(array: [5, 2, 7, 10, 30, 200, 156])