Swift) Sort 구현(2)

Quick / Merge Sort

새로운 배열에 저장하기 때문에 inout 키워드를 사용하지 않는다.

Quick Sort

• filter 함수 : 각 항목들을 비교하여 새로운 배열을 반환.

배열의 맨 앞의 수를 pivot 으로 설정해서 진행.

func quickSort(_ array: [Int]) -> [Int] {
    guard let first = array.first, array.count > 1 else { return array }
 
    let pivot = first
    let left = array.filter { $0 < pivot }
    let right = array.filter { $0 > pivot }
    
    return quickSort(left) + [pivot] + quickSort(right)
}

Merge Sort

배열의 갯수가 1개이하(재귀 탈출 조건)가 될 때까지 배열을 반으로 쪼갠 후 재귀 탈출하면 합병 정렬하면서 리턴해준다.

func mergeSort(_ array: [Int]) -> [Int] {
//재귀 탈출 조건.
    if array.count <= 1 { return array }
    let center = array.count/2
    let left = Array(array[0..<center])
    let right = Array(array[center..<array.count])
    
    return merge(mergeSort(left), mergeSort(right))
}

//합병
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var left = left
    var right = right
    var result: [Int] = []
    
    //한쪽 배열이 다 비워질 때까지.
    while !left.isEmpty && !right.isEmpty {
        //왼쪽이 가장 작기 때문.
        if left[0] < right[0] {
            result.append(left.removeFirst())
        } else {
            result.append(right.removeFirst())
        }
    }
    
    //왼쪽 배열의 요소가 남은 경우
    if !left.isEmpty {
        result.append(contentsOf: left)
    }
    if !right.isEmpty {
        result.append(contentsOf: right)
    }
    
    return result
}
}

출처

출처ㅣhttps://babbab2.tistory.com/101?category=908012

출처ㅣhttps://babbab2.tistory.com/102?category=908012