[Swift] (분할 정복) 퀵 정렬 구현해보기

이글은 비전공자 취준생이 개인적인 공부를 위해 작성한 글입니다.

자세한 내용은 https://babbab2.tistory.com/101 이곳에서 확인해주세요!

모든 이미지의 출처는 위의 티스토리임을 밝힙니다.

분할 정복

문제를 나눌 수 없을 때까지 나누어서 풀고, 나누어서 푼 문제를 다시 합병하여 답을 얻는 알고리즘

하양식 접근법으로 일반적으로 재귀함수로 구현합니다.

퀵 정렬

하나의 리스트를 pivot(기준점)을 기준으로 2개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

2개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게하는 방법입니다.

 

쉽게 생각하면 배열을 분할하고 정렬한 다음, 다시합치는 방법인 것 같습니다.

 

퀵정렬의 순서는 아래와 같습니다.

1. 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모읍니다.
2. 위에서 모은 왼쪽(left), 오른쪽(right)의 갯수가 1개 이하가 될 때까지 위 작업을 재귀로 반복합니다.
3. 재귀 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴합니다.

이해를 돕기 위한 예시

먼저, 가장 첫번째 Index를 pivot(기준점)으로 잡습니다.

그리고 pivot보다 작은 요소들은 왼쪽(left)이라는 배열에, 큰 요소들은 오른쪽(right)라는 배열에 모읍니다.

이 나눠놓은 left, right 배열을 다시 재귀시킵니다. (나눠진 left, right의 갯수가 1개 이하가 될 때까지)

각각의 left 모음이 갯수 1개가 되었기 때문에 재귀의 탈출 조건에 의해 더이상 재귀하지 않습니다.

이제 return 조건에 따라 left + pivot + right가 return 됩니다.

이렇게 차례대로 재귀함수가 return되다보면, 마지막에는 최종적으로 정렬된 배열이 return됩니다.

코드로 구현

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)
}

시간복잡도

퀵 정렬의 시간복잡도는 O(nlogn)입니다.

그런데 만약 첫번째 index인 pivot이 가장 크거나 가장 작으면 모든 데이터를 비교해야해서 O(n^2)이라고 합니다.