[알고리즘] 2-4 퀵정렬 / 병합정렬

1. 분할 정복

알고리즘이라기보다는 방법이다. 뒤에서 배울 알고리즘(퀵정렬과 병합정렬)에 쓰이는. 재귀와 비슷한데, 문제를 비슷한 크기로 쪼개어 푼다.

 

1-1 분할정복의 과정

① devide : 기존 문제를 작은 부분 문제들로 나눔
② conquer : 각 부분문제를 해결
③ combine : 부분 문제들의 솔루션을 통해 기존 문제를 해결

 

2. 병합정렬

예시로 설명하는 것이 더 쉽다. 봅시다.

다음과 같은 숫자 리스트를 정렬하고자 한다.

[4,2,6,3,7,8,5,1]

 

① 입력값을 반으로 여러번 쪼갠다

[4,2,6,3,7,8,5,1]

--> [4,2,6,3], [7,8,5,1]

--> [2,4], [3,6], [7,8], [5,1]

가장 작게 쪼개졌다!

 

③ 잘게 쪼갠 아이템을 정렬한다

 [2,4], [3,6], [7,8], [1,5]
--> [2,3,4,6], [1,5,7,8]

--> [1,2,3,4,5,6,7,8]

 

 

3. 퀵정렬

중간에 있는 수를 하나 정하여(pivot) 왼쪽에는 그보다 작은 수들을, 오른쪽에는 그보다 큰 수들을 배치한다. 쪼개진 왼쪽과 오른쪽에도 각각 pivot을 정하고 그를 기준으로 작은 수와 큰 수를 이동시킨다. 이 과정을 계속 반복하는 것이다.

 

4. 병합정렬과 퀵정렬 중 뭐가 더 좋은가?

- 빠르기

퀵정렬이 더 빠르다. 하지만 pivot을 잘못 설정하면 불균형하게 분할정복을 시도하기 때문에 성능이 안좋아질 수 있다. 

 

- 안정성

병합정렬이 더 안정적이기에 중복된 데이터들이 있을 때 적합하다.