[swift] Swift에서 퀵 정렬 알고리즘을 구현하는 방법

05 Dec 2023

swift

퀵 정렬(Quick Sort)은 효율적인 정렬 알고리즘으로 알려져 있습니다. 이번 글에서는 Swift 언어를 사용하여 퀵 정렬 알고리즘을 구현해보겠습니다.

퀵 정렬 알고리즘 이해하기

퀵 정렬은 분할 정복(Divide and conquer) 방법을 사용하여 리스트를 정렬합니다. 아래는 퀵 정렬의 주요 단계입니다.

리스트에서 하나의 원소를 선택하여 pivot으로 설정합니다. (보통은 첫 번째 원소를 pivot으로 사용합니다.)
pivot을 기준으로 작은 값은 pivot 왼쪽에, 큰 값은 pivot 오른쪽에 위치시킵니다.
pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 각각 재귀적으로 퀵 정렬합니다.
모든 재귀 호출이 끝나면 정렬이 완료됩니다.

Swift로 퀵 정렬 구현하기

func quickSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else {
        return array // 원소가 하나 이하면 이미 정렬된 상태
    }
    
    let pivot = array[array.count / 2] // pivot 설정
    
    let lesser = array.filter { $0 < pivot } // pivot보다 작은 값들
    let equal = array.filter { $0 == pivot } // pivot과 같은 값들
    let greater = array.filter { $0 > pivot } // pivot보다 큰 값들
    
    return quickSort(lesser) + equal + quickSort(greater) // 재귀 호출을 통해 정렬된 리스트를 합치기
}

위의 코드는 제네릭(Generic) 함수로, 모든 Comparable 프로토콜을 채택하는 데이터 타입에 대하여 동작합니다. 입력으로 주어진 배열을 작은 값, 같은 값, 큰 값으로 분류한 뒤, 재귀 호출을 통해 각각을 퀵 정렬하고 다시 합칩니다.

퀵 정렬 사용 예시

아래는 위에서 구현한 퀵 정렬 함수를 사용해보는 예시입니다.

let unsortedArray = [5, 9, 1, 3, 10, 7]
let sortedArray = quickSort(unsortedArray)
print(sortedArray) // [1, 3, 5, 7, 9, 10]

입력으로 주어진 배열이 [5, 9, 1, 3, 10, 7]일 때, 퀵 정렬을 수행하면 [1, 3, 5, 7, 9, 10]이라는 정렬된 배열이 출력됩니다.

마무리

Swift에서 퀵 정렬 알고리즘을 구현하는 방법에 대해 알아보았습니다. 퀵 정렬은 속도가 빠른 정렬 알고리즘 중 하나로, 대용량의 데이터를 정렬할 때 자주 사용됩니다. 본인의 프로젝트에 퀵 정렬을 적용해보고 성능을 비교해보는 것도 좋은 아이디어입니다.

더 자세한 내용은 다음 참고 자료를 확인하시기 바랍니다.

감사합니다.