Algorithm) 퀵 정렬(Quick Sort) in Swift

퀵 정렬(Quick Sort, 평균적으로 O(nlog n) 의 속도)은 정렬 알고리즘의 한 종류다. 

O(n²) 의 속도를 나타내는 선택 정렬보다 훨씬 빠르고 실제로도 자주 사용된다.

물론 퀵 정렬도 최악의 경우에는 O(n²) 의 속도를 내지만 그래도 평균과 최악 최선이 O(n²) 인 것 보다 좋지 않은가??

 

또한 퀵 정렬을 구현하기 위해서는 분할 정복 전략(divide and conquer)을 사용한다.

뭔가 나눠서 하나씩 내 것으로 만든다는 듯한 느낌을 주는 전략이다.

 

일단 코드를 보면서 이야기해보자.

let sampleArray = [4, 7, 9, 2, 3, 5, 6, 1, 8]

func quickSort(array: [Int]) -> [Int] {
    
    if array.count < 2 { // 배열이 비어있거나 하나만 있는 경우는 이미 '정렬'
        return array
    } else {
        let pivot = array[0] // 피봇의 기준이 무엇이냐에 따라 정렬의 과정도 달라진다. 일단 첫번째(4)를 기준
        let less = array.filter { $0 < pivot } // 피봇을 기준으로 피봇보다 같거나 작은 수들을 less 에 담는다.
        let greater = array.filter { $0 > pivot} // 피봇을 기준으로 피봇보다 같거나 큰 수들을 greater 에 담는다.
        return quickSort(array: less) + [pivot] + quickSort(array: greater) // 위의 과정을 반복한다.
    }
}

print(quickSort(array: sampleArray))

 

일단, 퀵 정렬을 이해하기 위해서는 '재귀(Recursion)'에 대한 이해가 필요하다.

또한 스위프트에서 제공하는 고차 함수 'filter' 가 어떻게 작동하는지 이해가 필요하다.

구글 집단 지성을 이용해 위 내용을 공부했다는 가정 하에 진행하도록 하겠습니다.

 

아 잠깐.. '분할 정복 전략'이 뭔데?

문제가 되는 부분을 잘게 잘게 쪼개서 쪼개는 아무 의미가 없기 직전까지(이를 기본 단계라 하자)

나눠주는 것이다. 밑을 읽어내려가면서 이해해보도록 하자.

 

 

Case 1. 배열이 비어있거나 하나만 있는 경우는 이미 '정렬'

if array.count < 2 {
	return array
}

이건 뭐.. 이해하기 어렵지 않은 부분이다.

배열이 비어있으면 정렬을 하지 않아도 되고, 배열에 요소가 1개 밖에 없으면 정렬을 할 필요가 없는, 어찌보면 '정렬된' 상태이지 않은가?

그래서 만약 배열의 크기(길이)가 2보다 작을 때는 함수의 Parameter 로 넣어준 array 를 그대로 반환한다.

이 부분은 guard 문을 사용한다면 다음과 같이 나타낼 수도 있다. 

guard array.count > 1 else {
	return array
}

 

Case 2. 기준 원소를 중심으로 작은 수와 큰 수를 나눈다.

 

} else {
        let pivot = array[0] // 피봇의 기준이 무엇이냐에 따라 정렬의 과정도 달라진다. 일단 첫번째(4)를 기준
        let less = array.filter { $0 < pivot } // 피봇을 기준으로 피봇보다 같거나 작은 수들을 less 에 담는다.
        let greater = array.filter { $0 > pivot} // 피봇을 기준으로 피봇보다 같거나 큰 수들을 greater 에 담는다.
        return quickSort(array: less) + [pivot] + quickSort(array: greater) // 위의 과정을 반복한다.
}

 

일단 배열에서 하나를 골라줘야 한다. 이를 기준 원소(Pivot)이라고 한다.

Pivot 의 선택 방법은 다양하다. 뭐 여러가지 방식이 있겠지만, 여기서는 배열의 가장 첫번째 숫자(array[0])를 pivot 으로 사용했다.

첫번째 숫자는 4이다. 자 그럼 이 4이자 동시에 pivot인 이 친구를 기준으로 삼았다.

그 다음 배열에서 pivot 기준점보다 작은 경우를 필터링해 배열에 다시 담는 less 와

배열에서 pivot 기준점보다 큰 경우를 필터링해 배열에 다시 담는 greater 를 구해준다.

 

자, 그러면 여기서 크게 3가지로 나눠볼 수 있겠다.

- pivot == 기준 원소

- pivot 보다 작은 숫자들로 이루어진 하위 배열 less

- pivot 보다 큰 숫자들로 이루어진 하위 배열 greater

 

그럼 이를 합쳐주기 위해서 return 부분에 정의한 내용이 실행된다.

 

Q. 필터링 했는데 왜 또 함수를 재귀로 실행시켜주나요?

왜냐하면 지금 필터링을 한 것이지, 정렬을 했다고는 말 하지 않았기 때문이다.

필터링한 부분에서 다시 기준 원소를 잡고 그 기준 원소를 중심으로 작은 수와 큰 수로 나뉘게 된다.

이러한 과정이 계속 진행되다가 결국 첫 if array.count < 2 부분에 걸려서 배열의 반환되면서 종료된다는 원리.

 

 

Case 3. 작동 예제 with 썰

let sampleArray = [4, 7, 9, 2, 3, 5, 6, 1, 8]

 

자 위 코드를 바탕으로 예제 썰을 풀어보도록하자.

일단 이 quickSort 라는 함수에 위와 같은 배열을 Parameter 로 넣었다.

이 배열의 count 는 9 이기 때문에 if 문을 지나쳐 else 문으로 가게 되었다.

pivot 은 배열의 가장 첫번째 인덱스(0)인 '4' 가 되었다.

less 에는 pivot 보다 작은 숫자들이 들어가게 된다. 그것은 [2, 3, 1] 이다.

나머지는 greater 배열에 들어가게 되겠죠? [7, 9, 5, 6, 8]

이제 return 을 만나 quickSort(array: less) 부분이 실행된다. 

 

Q. 나머지 부분은요? A. 'Stack'에 대해 공부하고 오시길 바란다.

 

여기까지가 첫 타임.

 

자 [2, 3, 1] 이라는 배열이 파라미터로 전달된 quickSort 함수가 실행되었다.

pivot 은 '2'

less 는 '1'

greater 는 '3'

또 이제 return 을 만나 [1] 이 Parameter 로 전달되는 quickSort 함수가 시작된다. 하지만 count 가 1이라서 2보다 작기 때문에 함수는 종료.. 그럼 이제 두 번째 타임의 return 에서 quickSort(array: less) 부분이 종료되고 그 다음 + [pivot] + 부분이 [1] 과 합쳐져

[1, 2] 가 되었고 그 뒤의 quickSort(array: greater) 도 또한 count 가 1이기 때문에 [3]을 리턴하고 앞의 [1, 2] 와 합쳐져

결국 [1, 2, 3] 을 완성한다

 

이런 원리로 정렬이 된다고 보시면 되겠다.

퀵 정렬 끝. 

 

 

 

 

 

혹시 틀린게 있다면 지적 감사드리겠습니다...