Sidebar

Recent changes
Trace:

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
merge_sort [2016/06/07 12:38] – ledyxmerge_sort [2016/06/07 13:03] (current) – 이전 ledyx
Line 1: Line 1:
-= Merge Sort (병합 정렬) = 
- 
-{{tag>Algorithm Sort}} 
- 
-<code java> 
-A[p ... r]을 정렬한다. 
-{ 
- if(p < r) then { 
- q ← (p+r)/2 // 1.중간 지점 계산 
- mergeSort(A, p, q); // 2-1. 전반부 정렬 
- mergeSort(A, q+1, r) // 2-2. 후반부 정렬 
- merge(A, p, q, r); // 3. 병합 
- } 
-} 
- 
-merge(A[], p, q, r) 
-{ 
- 정렬된 부분배열 2-1, 2-2를 병합 후 
- 재정렬, 하나의 배열로 만든다. 
-} 
-</code> 
- 
- 
-== Java 구현 == 
-<sxh java> 
-import java.util.ArrayList; 
- 
-public class MergeSort { 
- 
- public static void main(String[] args) { 
- int[] arr = {100, 99, 97, 1, 3, 0, -15, 30, 36/6, 7, 2}; 
- 
- mergeSort(arr, 0, arr.length-1); 
- 
- for (int i = 0; i < arr.length; i++) 
- System.out.println(arr[i] + " "); 
- } 
- 
- private static void mergeSort(int[] arr, int startIndex, int endIndex) { 
- if (startIndex < endIndex) { 
- int middleIndex = (startIndex + endIndex) / 2; 
- 
- mergeSort(arr, startIndex, middleIndex); 
- mergeSort(arr, middleIndex + 1, endIndex); 
- 
- merge(arr, startIndex, middleIndex, endIndex); 
- } else 
- return; 
- } 
- 
-/** 
- 1. 두 배열을 합한 크기만큼의 비어있는 임시 배열 준비 
- 2. 첫번째 요소끼리 비교하여 작은 요소를 "1"에 추가. 정렬된 원소 삭제. 
- 3. 양쪽 배열이 빌 때까지 "2" 반복. 
-*/ 
- private static void merge(int[] arr, int startIndex, int middleIndex, int endIndex) { 
- int L_startIndex = startIndex; 
- int R_startIndex = middleIndex + 1; 
- int tempList_index = 0; 
- 
- ArrayList<Integer> tempList = new ArrayList<Integer>(); // 동적 배열 
- 
- while (L_startIndex <= middleIndex && R_startIndex <= endIndex) { 
- if (arr[L_startIndex] < arr[R_startIndex]) 
- tempList.add(arr[L_startIndex++]); 
- else 
- tempList.add(arr[R_startIndex++]); 
- } 
- 
- while (L_startIndex <= middleIndex) 
- tempList.add(arr[L_startIndex++]); 
- 
- while (R_startIndex <= endIndex) 
- tempList.add(arr[R_startIndex++]); 
- 
- while (startIndex <= endIndex) 
- arr[startIndex++] = tempList.get(tempList_index++); 
- 
- tempList.removeAll(tempList); // 원소 전부 제거 
- } 
-} 
-</sxh> 
- 
- 
- 
-== C 구현 == 
-<sxh c> 
-#include <stdio.h> 
-#include <stdlib.h> 
- 
-void mergeSort(int arr[], int start_index, int end_index); 
-void merge(int arr[], int start_index, int middle_Index, int end_index); 
- 
-void main() { 
- int arr[] = {100, 99, 97, 1, 3, 0, -15, 30, 36/6, 7, 2}; 
- int length = sizeof(arr)/sizeof(int); 
- int i=0; 
- 
- mergeSort(arr, 0, length-1); 
- 
- for (i=0 ; i<length ; i++) 
- printf("%d ", arr[i]); 
- 
- printf("\n"); 
-} 
- 
-void mergeSort(int arr[], int start_index, int end_index) 
-{ 
- if(start_index < end_index) { 
- int middle_index = (start_index+end_index)/2; // 1.중간지점 계산  
- 
- mergeSort(arr, start_index, middle_index); // 2-1. 전반부 정렬 
- mergeSort(arr, middle_index+1, end_index); // 2-2. 후반부 정렬 
- 
- merge(arr, start_index, middle_index, end_index); // 3. 병합 
- } 
- else 
- return; // start_index >= end_index, 원소가 딱 하나 남았을 때 탈출! 
-} 
- 
-/** 
-1. 두 배열을 합한 크기만큼의 비어있는 임시 배열 준비 
-2. 첫번째 요소끼리 비교하여 작은 요소를 "1"에 추가. 정렬된 원소 삭제. 
-3. 양쪽 배열이 빌 때까지 "2" 반복. 
-**/ 
-void merge(int arr[], int start_index, int middle_index, int end_index) 
-{ 
- int LStart_index = start_index; //전반부 시작 인덱스 
- int RStart_index = middle_index+1; //후반부 시작 인덱스 
- 
- int* tempArr = (int*) malloc(sizeof(int) * (end_index - start_index+1)); // 1. 동적 배열 준비 
- int tempArr_index = 0; 
- 
- while(LStart_index <= middle_index && RStart_index <= end_index) { 
- if(arr[LStart_index] < arr[RStart_index]) 
- tempArr[tempArr_index++] = arr[LStart_index++]; 
- else 
- tempArr[tempArr_index++] = arr[RStart_index++]; 
- } 
- 
- while (LStart_index <= middle_index) 
- tempArr[tempArr_index++] = arr[LStart_index++]; 
- 
- while (RStart_index <= end_index) 
- tempArr[tempArr_index++] = arr[RStart_index++]; 
- 
- 
- // 2-1. "원배열 = 임시 배열" 복사. 
- tempArr_index = 0; 
- while (start_index <= end_index) 
- arr[start_index++] = tempArr[tempArr_index++]; 
- 
- free(tempArr); // 2-2. 원소 삭제 
-} 
-</sxh> 
  
merge_sort.1465303080.txt.gz · Last modified: (external edit)