퀵 정렬

• 정렬 알고리즘의 꽃은 퀵 정렬이라고 한다!

퀵 정렬은 분할 정복 알고리즘에 속한다.

분할정복이란

문제를 나눌 수 없을 때까지 나누어서 풀고, 나누어서 푼 문제를 다시 합병하여 답을 얻는 알고리즘
하향식 접근법으로, 일반적으로 재귀 함수로 구현

퀵, 합병 모두 이것에 속한다.

퀵정렬이란?

재귀 함수를 사용한다.

ⓛ 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모음

② 위에서 모은 왼쪽(left), 오른쪽(right)의 갯수가 1개 이하가 될 때까지 위 작업을 재귀로 반복함

③ 재귀 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함

구현하기

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)으로 앞선 세개 정렬보다는 아주 빠른 방법이다.

합병 정렬

분할 정도.
이것두 재귀를 싸용한다.
① 배열을 절반으로 잘라, 두 배열로 나눔

(배열의 갯수가 7같이 홀수일 경우, 3개&4개로 나눔)

② 배열의 갯수가 1개 이하일 때까지 위 작업을 재귀함수로 반복함

③ 재귀 함수는 나눠진 두 배열을 합병 정렬을 이용해 정렬하고 리턴함
https://blog.kakaocdn.net/dn/ptiSD/btqTPypRec1/ccLgr58qKzW6KYxw2oeoc1/img.gif