# 정렬

###### tags: `algo`

// 삽입 정렬
public func insertionSort<T: Comparable>(_ list: inout [T]) {
    
    if list.count <= 1 {
        return
    }
    
    for i in 1..<list.count {
        let x = list[i]
        var j = i
        while j > 0 && list[j - 1] > x {
            list[j] = list[j - 1]
            j -= 1
        }
        list[j] = x
    }
}

// 삽입 정렬은 인덱스를 하나씩 추가해주면서, 해당하는 인덱스 앞을 정렬해주며 인덱스를 마지막까지 정렬해주는 정렬 방식이다.

// 병합 정렬
func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }    // 1
    
    let middleIndex = array.count / 2              // 2
    
    let leftArray = mergeSort(Array(array[0..<middleIndex]))             // 3
    
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  // 4
    
    return merge(leftPile: leftArray, rightPile: rightArray)             // 5
}

func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
    // 1
    var leftIndex = 0
    var rightIndex = 0
    
    // 2
    var orderedPile = [Int]()
    orderedPile.reserveCapacity(leftPile.count + rightPile.count)
    
    // 3
    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] < rightPile[rightIndex] {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
        } else {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }
    
    // 4
    while leftIndex < leftPile.count {
        orderedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < rightPile.count {
        orderedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }
    
    return orderedPile
}

// 퀵 소트
func quicksort<T: Comparable>(_ list: [T]) -> [T] {
    guard list.count > 1 else { return list }
    
    let pivot = list[list.count/2]
    let less = list.filter { $0 < pivot }
    let equal = list.filter { $0 == pivot }
    let greater = list.filter { $0 > pivot }
    
    return quicksort(less) + equal + quicksort(greater)
}