정렬 : 분할 정복 기법 (Divide - and - Conquer), 병합 정렬(Merge sort), 퀵 정렬(Quick sort)

 

* 이 글은 "한국항공대학교 - 알고리즘해석 및 설계" 정렬에 나온 내용을 바탕으로 작성하였습니다.

 

1. 분할 정복 기법 (Divide - and - Conquer)

 

- 착안점 : 문제의 크기가 커지면 더 풀기가 어렵다.

- 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법

- 순환적(recursive)으로 문제를 푸는 하향식(Top - Down) 접근 방법

- 분할 정복의 설계 전략

(1) 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다.

(2) 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.

(3) 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을 구한다.

- 정렬 문제에 대한 분할 정복

기법 : 병합 정렬(Mergesort), 퀵 정렬(Quicksort)가 있다.

 

 

 

 

2. 병합 정렬(Merge sort)

 

- 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택합니다. 즉 일단 정확히 반으로 나누고 나중에 정렬하는 것입니다.

- 과정 설명

(1) 리스트의 길이가 0 or 1이면 이미 정렬된 것으로 본다.

(2) 그렇지 않은 경우에는 정렬되지 않은 리스트를 전반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

(3) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.

(4) 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

 

- 병합 정렬 C++ 코드, Python code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int size;
int sorted[8];
int count = 0;

void merge(int a[], int m, int middle, int n) {
	int i = m;
	int j = middle + 1;
	int k = m;

	while (i <= middle && j <= n) { //작은 순서대로 배열에 삽입
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

	if (i > middle) { //남은 데이터도 삽입
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}

	for (int t = m; t <= n; t++) { //정렬된 배열을 삽입
		a[t] = sorted[t];
	}
}

void mergeSort(int a[], int m, int n) { //분할 정복
	if (m < n) {
		int middle = (m + n) / 2;
		mergeSort(a, m, middle); //앞쪽 반
		mergeSort(a, middle + 1, n); //뒤쪽 반
		merge(a, m, middle, n); //오름차순으로 정렬된 두 리스트 A, B의 병합
	}
}

int main() {
	int array[8] = { 7, 6, 5, 8, 3, 10, 9, 1 };
	mergeSort(array, 0, 7);
	for (int i = 0; i < 8; i++) {
		printf("%d ", array[i]);
	}
}

#오름차순으로 정렬된 두 리스트 A, B의 병합
def merge(A, B):
    if (len(A) == 0): //A가 비어 있다면 B를, B가 비어 있다면 A를 리턴
        return B
    if (len(B) == 0):
        return A
    if (A[0] < B[0]): //맨 처음 원소를 비교하고 작은 쪽을 리스트에 넣는다.
        return [A[0]] + merge(A[1:], B) //이 원소를 제거하고 재귀적으로 진행
    else:
        return [B[0]] + merge(A, B[1:])

def mergesort(L):
    if (len(L) == 1):
        return L
    return merge(mergesort(L[:int(len(L) / 2)]), mergesort(L[int(len(L) / 2):]))

 

 

- 병합 정렬의 정확성 / 시간 복잡도

 

(1) 정확성

- 기본 경우 : A, B 둘 중 하나가 비어 있는 경우

--> 나머지 하나는 이미 정렬되어 있으므로 병합 결과는 그 자신

- 귀납 단계 : A, B 모두 비어 있지 않은 경우

--> 리스트에 들어가는 원소는 모든 원소 중 가장 작다.

--> 재귀적으로 진행되는 과정에서, 리스트의 원소는 A, B 둘 중 하나는 원래보다 원소가

하나 적다. (리스트 A, B의 한 곳에서 계속 하나씩 원소를 빼기 때문에 언제가 종료됨.)

​

(2) 시간 복잡도, 공간 복잡도

- 두 리스트 병합의 시간 복잡

(1) 최적 : 두 리스트가 서로 교차되는 부분이 없을 때 n / 2

(2) 최악 : 두 리스트가 서로 모두 교차할 때 n

- 실제 정렬은 맨 마지막에는 원소 하나를 가지는 리스트, 정렬된 리스트를 연속적으로 병합

- 점화식

--> T(n) = 2 T(n / 2) + n, T(n) = Θ(n log n)

--> n / 2 개의 리스트 2개를 정렬하고, 이를 합치는데 n번 비교

- 특징

(1) 입력의 형태에 상관없이 언제나 같은 시간 복잡도 보장

(2) 언제난 문제의 크기가 1 / 2로 줄어듬.

(3) 실제로는 원소들이 더 자주 움직이므로 시간이 더 많이 걸림.

Name	Best	Avg	Worst
병합 정렬(Bubble sort)	n log n	n log n	n log n

- 두 리스트 병합의 공간복잡도

(1) A, B를 복사하는 경우 2n

(2) linked list로 구현하는 경우 n (A, B의 원래 내용은 파괴됨.)

 

- 병합 정렬의 장, 단점

(1) 장점

- 안정적인 정렬 방법 : 데이터의 분포에 영향을 덜 받는다. 즉, 입력의 형태에 상관이 없이 시간은 동일

- 만약 원소를 연결 리스트로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있다.

- 따라서 크기가 큰 원소를 정렬할 경우에 연결 리스트를 사용한다면 효율적이다.

​

(2) 단점

- 원소를 배열로 구성하면, 임시 배열이 필요하다.

- 원소들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

 

2. 퀵 정렬(Quick sort)

 

- 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬을 합니다. 다시 말해 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다.

- 과정 설명

(1) 리스트 안에 있는 한 원소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.

(2) pivot을 기준으로 pivot보다 작은 원소들은 모두 pivot의 왼쪽으로 옮겨지고, pivot보다 큰 원소들은 모두

pivot의 오른쪽으로 옮겨진다. ( pivot보다 작은 원소들, pivot, pivot보다 큰 원소들)

(3) pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.

--> 분화된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.

--> 부분 리스트에서도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분 리스트로 나누는 과정을 반복

(4) 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

--> 리스트의 크기가 0 or 1이 될 때까지 반복한다.

 

ex) 5 1 3 7 6 2 8 4 (초기값)

--> 1회 처리 : 5 1 3 7 6 2 8 4 : pivot은 5

_ 1 3 7 6 2 8 4 : 5를 비우고, 오른쪽부터 왼쪽으로 이동 기준보다

크면 그대로, 작으면 빈자리로

4 1 3 7 6 2 8 _ : 왼쪽부터 오른쪽으로 이동 기준보다 작으면 그대로,

크면 빈 자리로

4 1 3 _ 6 2 8 7

4 1 3 2 _ 6 8 7

4 1 3 2 5 6 8 7 : 마지막 빈 자리에 기준을 넣는다.

--> 2회 처리 : 1회 처리의 pivot 5를 기준으로 왼쪽 오른쪽을 다시 재귀적으로 반복

 

- 퀵 정렬 C++ 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int number = 10;
int data[] = { 1, 10, 4, 2, 3, 5, 9, 8, 7, 6 };

void quickSort(int data[], int start, int end) {
	if (start >= end) //원소가 1개인 경우 그대로 두기
		return;

	int key = start;
	int i = start + 1, j = end, temp;

	while (i <= j) {
		while (i <= end && data[i] <= data[key]) { //키 값보다 큰 값을 만날 때까지
			i++;
		}
		while (j > start && data[j] >= data[key]) { //키 값보다 작은 값을 만날 때까지
			j--;
		}
		
		if (i > j) { // 현재 엇갈린 상태면 키 값과 교체
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else { // 엇갈리지 않았다면 i와 j를 교체
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	
	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}

int main() {
	quickSort(data, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d ", data[i]);
	}
	return 0;
}

 

 

- 퀵 정렬의 시간 복잡도

(1) 시간 복잡도

- 가장 좋을 때 : 기준의 왼쪽, 오른쪽에 같은 수의 원소가 이동함

--> T(n) = 2 T(n / 2) + n, T(n) = Θ(n log n)

 

- 가장 나쁜 경우 : 기준의 왼쪽 or 오른쪽 한 쪽으로만 원소가 솔림

--> T(n) = 2 T(n - 2) + n, T(n) = Θ(n^2)

 

- 평균적인 경우 : 복잡

--> 극단적인 경우에도 T(n) = O(n log n)

--> T(n) = T(99 n / 100) + T(n / 100) + n : 99%가 한쪽으로 가고 1퍼가 다른 한쪽으로 가는 경우

--> 기준을 첫 번째 원소가 아니라 램덤으로 고름 : 가장 나쁜 경우를 피할 수 있는 확률이 높다.

Name	Best	Avg	Worst
병합 정렬(Bubble sort)	n log n	n log n	n ^ 2

 

- 퀵 정렬의 장점

(1) 장점

- 속도가 빠르다 : 다른 정렬 알고리즘과 비교했을 때 가장 빠르게 동작