[Swift] Quick Sort 구현해보기

[Swift] Quick Sort 구현해보기

---

퀵 정렬은 분할 정복 기법중에 하나다.

분할 정복이란 문제를 작은 두개의 문제로 분리하고, 각각 해결한 다음 결과를 모아서 문제를 해결하는 전략이다!

 

먼저 프로세스를 살펴보면

1. 배열 <가운데>에서 <피벗>이 될 하나의 원소를 고른다.

2. 피벗 앞에는 피벗보다 작은 값들이 오고, 피벗 뒤에는 큰 값이 오도록 배열을 두개로 나눈다.

--> 이렇게 배열을 두개로 나누는 걸 분할이라고 한다.

3. 분할된 두개의 작은 배열에 대해 재귀적으로 과정을 반복한다.

 

func quickSort(_ array: [Int]) -> [Int] {
    guard let first = array.first, array.count > 1 else { return array }
    let pivot = first
    let (left, right) = array.dropFirst().reduce(into: ([Int](), [Int]())) { result, element in
        if element < pivot {
            result.0.append(element)
        } else if element > pivot {
            result.1.append(element)
        } else {
            result.0.append(element)
        }
    }
    return quickSort(left) + [pivot] + quickSort(right)
}

 

결과

Input - [7,10,7,6,9,3,9,1]