퀵정렬 구현하기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. pivot이 배열을 절반으로 나눈다고 가정했을 때, 평균적으로 O(n log n) 시간 복잡도를 가지고,
2. 배열이 이미 정렬되어 있는 경우(최악의 경우), O(n ^ 2)의 시간복잡도를 가짐
3. pivot을 기준으로 크고 작은 배열로 나누게 되고, 다시 퀵정렬하는 재귀적인 패턴이므로, 재귀함수를 이용하여 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 퀵정렬 구현하기

//MARK: - Framework
import Foundation

//MARK: - Function
func getLeft(_ array: [Int], _ start: Int, _ end: Int, _ pivot: Int, _ left: inout [Int]) -> Int {
    var index: Int = 0
    for i in start...end {
        if array[i] <= pivot {
            left[index] = array[i]
            index += 1
        }
    }
    
    return index
}

func getRight(_ array: [Int], _ start: Int, _ end: Int, _ pivot: Int, _ right: inout [Int]) -> Int {
    var index: Int = 0
    for i in start...end {
        if array[i] > pivot {
            right[index] = array[i]
            index += 1
        }
    }
    
    return index
}

func quickSort(_ array: inout [Int], _ left: inout [Int], _ right: inout [Int], _ start: Int, _ end: Int) {
    //array의 start 번 째 값 부터 end 번 째 값 까지 퀵 정렬 하는 함수
    if start >= end {
        return
    }
    
    let pivot: Int = array[start]
    let leftCount: Int = getLeft(array, start + 1, end, pivot, &left)
    let rightCount: Int = getRight(array, start + 1, end, pivot, &right)
    
    for i in 0..<leftCount {
        array[start + i] = left[i]
    }
    
    array[start + leftCount] = pivot
    
    for i in 0..<rightCount {
        array[start + leftCount + 1 + i] = right[i]
    }
    
    quickSort(&array, &left, &right, start, start + leftCount - 1)
    quickSort(&array, &left, &right, start + leftCount + 1, end)
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    
    var answer: String = ""
    var array: [Int] = input.map { Int($0) ?? 0 }
    var left: [Int] = Array(repeating: 0, count: N)
    var right: [Int] = Array(repeating: 0, count: N)
    
    //MARK: - Process
    quickSort(&array, &left, &right, 0, N - 1)
    
    for i in 0..<array.count - 1 {
        answer += "\(array[i]) "
    }
    answer += "\(array[array.count - 1])"
    
    //MARK: - Output
    print(answer)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.