[알고리즘] 합병정렬과 퀵정렬(1) - 설명

분할통치법은 일반적인 알고리즘 설계기법의 일종으로 다음과 같은 해결절차를 가진다.

1. 분할(divide) : 입력 데이터 L을 둘 이상의 분리된 부분집합 L1, L2, ---으로 나눈다.

2. 재귀(recur) : L1, L2, ---각각에 대한 부문제를 재귀적으로 해결한다.

3. 통치(conquer) : 부문제들에 대한 해결을 합쳐 L의 해결을 구한다.

합병정렬(O(nlog n))은 분할통치법에 기초한 정렬 알고리즘이다.

힙정렬과 같이 비교에 기초한 정렬이지만, 힙정렬과는 다르게 우선순위 큐를 사용하지 않으며, 데이터를 순차적방식으로 접근한다.

합병정렬 알고리즘(mergeSort)는 세 단계로 이루어진다. (n개의 원소로 이루어진 입력 리스트L에 대해)

1. 분할 : 무순리스트 L을 각각 n/2개의 원소를 가진 두 개의 부리스트 L1과 L2로 분할

2. 재귀 : L1과 L2를 각각 재귀적으로 정렬

3. 통치 : L1과 L2를 단일 순서리스트로 합병

합병정렬 알고리즘은 실행 과정에서 이진트리 형태로 보일 수 있는데, 이 같은 이진트리를 합병 정렬 트리라고 한다.

예시)

6 1 8 2 3 5 7 4

6 1 8 2    3 5 7 4

6 1    8 2    3 5    7 4

6    1    8    2    3    5    7    4

1 6    2 8    3 5    4 7

1 2 6 8    3 4 5 7

1 2 3 4 5 6 7 8

퀼정렬(O(n^2))은 합병정렬과 마찬가지로 분할통치법에 기초한 정렬 알고리즘이다. 

힙정렬 알고리즘(quickSort)는 아래의 세 단계를 재귀적인 방식으로 수행하여 이루어진다. (입력리스트L에 대해)

1. 분할 : 입력리스트 원소 가운데 기준원소p를 택하여 L을 다음 세 부분으로 분할한다.

- LT(p보다 작은 원소들)

- EQ(p와 같은 원소들)

- GT(p보다 큰 원소들)

2. 재귀 : LT와 GT를 정렬한다

3. 통치 : LT, EQ, GT를 결합한다.

퀵정렬 알고리즘은 실행 과정에서 이진트리 형태로 보일 수 있는데, 이 같은 이진트리를 퀵 정렬 트리라고 한다.

예시)

6 1 8 2 3 5 7 4

6 1 2 3 5 4    8

1 2    6 5 4

2    4    6

1 2    4 5 6

1 2 3 4 5 6    8

1 2 3 4 5 6 7 8

퀵정렬은 제자리 퀵정렬을 통해서 기억장소 소요량을 최소화시킬 수 있다.

확률에 기초한 분석으로 얻은 실행시간을 기대실행시간이라 한다.

퀵정렬에서는 좋은호출과 나쁜호출이 있는데, 이에 따라 퀵정렬의 기대실행시간은 O(nlog n)이 된다.

예시)

7 2 9 4 3 6 7 1

2 4 3 1    7 9 7

좋은호출---------------------------

7 2 9 4 3 6 7 1

1    7 9 4 3 6 7

나쁜호출---------------------------

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
나쁜 기준 원소				좋은 기준 원소								나쁜 기준 원소

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사