목차
정렬이란?
- 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
- 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
① 데이터를 탐색할 때
② 리스트에 있는 다른 항목들을 비교할 때
분할 정복 Divide and Conquer
more learn
분할 정복은 말 그대로 문제를 ‘분할’ 해서 ‘정복’ 한 다음 정답을 ‘조합’해 나간다는 의미
- 분할 정복은 재귀를 활용하는 대표적인 알고리즘
병합정렬
전체를 한번에 정렬하기 어렵기 때문에 정렬이 편해질때 까지 잘게 쪼갬
- 분할 정복 Divide and Conquer의 진수를 보여주는 알고리즘
수도코드
function F(x):
if F(x)가 간단 then:
return F(x)를 계산한 값
--------------
정복 ➊
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값
------ ------------
조합 ➋ 분할 ➌
코드 설명
이 수도코드 내에서 분할, 정복, 조합의 역할을 구분해보면,
➊ 부분의 정복
➋ 부분의 조합
➌ 부분의 분할로 정리 가능 
시간 복잡도
최선과 최악 모두 O(n log n)인 사실상 완전한 Θ(n log n) 으로 일정한 알고리즘
평가
퀵 정렬보다는 느리지만
- 일정한 실행 속도의 장점
- 안정 정렬 Stable Sort 이라는 점에서 여전히 상용 라이브러리에 많이 쓰임
[장점]
- 데이터 분포에 영향을 덜 받는다
[단점]
- 임시배열 필요
- 데이터가 클 경우 이동횟수가 많아짐
구현
파이썬
def merge_sort(arr):
if len(arr) < 2:
return arr
#비교할 것들 분할
mid = len(arr) // 2
low_arr = merge_sort(arr[:mid])
high_arr = merge_sort(arr[mid:])
merged_arr = []
l = h = 0
# 하나하나 비교하며 병합
# 두개의 분할된 것들 중 작은것 추가
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
# 것들 추가
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
return merged_arr
자바
public class Merge_Sort {
public static void main(String[] args) {
int[] arr = { 10, 80, 91, 90, 70 };
/*원소를 반으로 나누는 함수*/
mergeSortDevide(arr, 0, arr.length - 1);
/*합병 정렬된 배열을 출력하는 함수*/
output_merge_arr(arr);
}
private static void mergeSortDevide(int[] arr, int left, int right) {
/*원소의 수가 2개 이상일경우 실행*/
if (left < right) {
/*반으로 나누기 위한 변수*/
int mid = (left + right) / 2;
/*앞(왼쪽)부분 재귀 호출*/
mergeSortDevide(arr, left, mid);
/*뒤(오른쪽)부분 재귀 호출*/
mergeSortDevide(arr, mid + 1, right);
/*원소를 Merge하는 함수*/
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int temp_index = left;
int[] temp = new int[arr.length];
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[temp_index++] = arr[i++];
} else {
temp[temp_index++] = arr[j++];
}
}
/*앞(왼쪽)부분 배열에 원소가 남아있는 경우*/
while (i <= mid) {
temp[temp_index++] = arr[i++];
}
/*뒤(오른쪽)부분 배열에 원소가 남아있는 경우*/
while (j <= right) {
temp[temp_index++] = arr[j++];
}
for (int index = left; index < temp_index; index++) {
arr[index] = temp[index];
}
}
private static void output_merge_arr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}