Swift - quick sort

- 퀵 정렬

 

퀵 정렬은 흔히 피봇(pivot)이라고 불리는 임의의 기준값을 사용

 

func quicksort(_ arr: [Int]) -> [Int] {
    // 기본단계: 원소의 개수가 0이나 1이면 정렬된 상태
    if arr.count < 2 {
        return arr
    }

    // 재귀단계:
    // less 기준 원소보다 작거나 같은 원소로 이루어진 하위배열
    // greater 기준 원소보다 큰 원소로 이루어진 하위배열
    let pivot = arr[0]
    var less = [Int]()
    var greater = [Int]()
    for i in arr[1...] {
        if i <= pivot {
            less.append(i)
        } else {
            greater.append(i)
        }
    }

    return quicksort(less) + [pivot] + quicksort(greater)
}

print( quicksort([10,5,2,3]) ) // -> [2,3,5,10]
print( quicksort([6,5,1,4,7,2,3]) ) // -> [1,2,3,4,5,6,7]