반응형 합병 정렬2 합병 정렬(Merge Sort) 구현 #include #include #include void merge(int, int, int *, int *, int *); void mergesort(int n, int *); void multiplication(); void mergesort(int n, int *S) { int h = n/2; int m = n-h; int *U = (int *)malloc(h*sizeof(int)); int *V = (int *)malloc(m*sizeof(int)); if(n>1) { int i; for(i=0; i 2007. 4. 2. 합병 정렬(Merge Sort) u 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함 u 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임 u 두 부분배열의 크기가 동일하도록 분할함 u 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨 u 순차적 방식에 의해 데이터를 접근함 u 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능 u N 에 비례하는 추가 기억장소가 필요함 u 안정적이지만 제자리 정렬은 아님 MergeSort(a[], l, r) if (r > l) then { m ← (r+l)/2; MergeSort(a[], l, m); MergeSort(a[], m+1, r); Merge(a[], l, m, r); } end MergeSort() Merge(a.. 2007. 4. 2. 이전 1 다음 반응형
