자료구조, 알고리즘/기본다지기
[정렬] 합병 정렬 (Merge Sort) - 개념, 시간복잡도, 구현
민쓰
2018. 9. 10. 16:56
합병 정렬 개념
배열을 절반으로 나누어 각각을 정렬한 후, 합친다.
합병 정렬의 시간복잡도
재귀적으로 구해야 한다.
1. 왼쪽 합병정렬 = T(n/2)
2. 오른쪽 합병정렬 = T(n/2)
3. 합친다 = O(n)
* T(n) = n개의 숫자를 합병정렬할 때의 시간복잡도
* T(n) = 2 x T(n/2) + O(n) // 점화식
= 2(2T(n/4) + O(n/2)) + O(n)
= 4T(n/4) + 2O(n) // 1번 대입
= 4(2T(n/8) + O(n/4)) + 2O(n)
= 8T(n/8) + 3O(n) // 2번 대입
...... // k번 대입 k+1 = log n
= n x T(1) + log n x O(n)
= n x O(1) + O(n log n)
= O(n) + O(n log n)
*
합병 정렬 구현 코드
import java.util.Scanner; public class SortMerge { // 합병정렬 : 배열을 절반으로 나누어 각각을 정렬한 후, 합침 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] data = new int [100]; for(int i=0; i<n; i++){ data[i] = sc.nextInt(); } mergeSort(data, 0, n-1); for(int i=0; i<n; i++){ System.out.print(data[i]+" "); } } // data의 start부터 end까지를 합병정렬하는 함수 private static void mergeSort(int[] data, int start, int end) { if(start >= end) // 숫자가 한 개 남았을 때 return; else{ int mid = (start+end)/2; mergeSort(data, start, mid); // 1. 왼쪽 절반 합병정렬 mergeSort(data, mid+1, end); // 2. 오른쪽 절반 합병정렬 merging(data, start, mid, mid+1, end);// 3. 둘을 합침 } } // 정렬된 반쪽들을 정렬해서 하나로 합치는 함수 private static void merging(int[] data, int s1, int e1, int s2, int e2) { int p, q; // 현재 최솟값을 가리키는 변수들 int [] temp = new int[100]; // 합쳐진 결과를 저장하는 임시배열 int tempIndex = 0; p = s1; // 왼쪽 절반의 시작점 q = s2; // 오른쪽 절반의 시작점 while(p <= e1 && q <= e2) { if(data[p] <= data[q]){ temp[tempIndex++] = data[p]; p++; } else{ temp[tempIndex++] = data[q]; q++; } } if(p > e1){// q에 남은 숫자가 있는 경우 for(int i=q; i<=e2; i++){ temp[tempIndex++] = data[i]; } } else{// p에 남은 숫자가 있는 경우 for(int i=p; i<=e1; i++){ temp[tempIndex++] = data[i]; } } // temp[] 완성이 되었으니 data[]에 복사 for(int i=s1; i<=e2; i++){ data[i] = temp[i-s1]; //data[] 는 0부터 시작하는 것이 아님, temp는 0부터 시작 } } }