-
합병 정렬 (Merge Sort) 알고리즘Computer Science/자료구조&알고리즘 2021. 2. 17. 15:28
분할정복에 기반한 정렬 알고리즘.
배열을 모조리 분할한 다음에, 도로 합치면서 정렬이 이루어진다.분할 단계와 합병 단계로 나뉜다.
수도코드
merge_sort(int a[], int len){
if(len == 1){
return;
}// 분할 단계
merge_sort(a, len/2);
merge_sort(a + len/2, len - len/2);// 합병 단계
int b[len];
int i = 0, j = len/2, k;
for(k = 0; k < len; k++){
if(i < len/2 && (j >= len || a[i] <= a[j])){
b[k] = a[i]; i++;
}
else{
b[k] = a[j]; j++;
}
}
for(k = 0; k < len; k++){
a[k] = b[k];
}
}시간 복잡도 : 배열을 분할하는 단계의 개수는 log n이다. 그리고 각 단계에서 비교 및 대입 연산을 n회씩 한다.
그러므로 시간 복잡도는 O(n log n)이 된다.
'Computer Science > 자료구조&알고리즘' 카테고리의 다른 글
힙 정렬 (Heap Sort) 알고리즘 (0) 2021.02.17 퀵 정렬 (Quick Sort) 알고리즘 (0) 2021.02.17 힙(heap)의 삽입과 삭제 (0) 2021.02.16 BFS (Breadth First Search) : 너비 우선 탐색 (0) 2021.02.15 DFS (Depth First Search) : 깊이 우선 탐색 (0) 2021.02.15