Winwoo's Story

병합 정렬

1. 병합 정렬이란?

- 분할 정복 ( DAC - Divide And Conquer ) 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법

* 분할정복이란? 복잡한 문제를 분할 하여 정복 후 결합하는 방법

∙ 1단계 분할(Divide) 해결이 용이한 단계까지 문제를 분할해 나간다.

∙ 2단계 정복(Conquer) 해결이 용이한 수준까지 분할된 문제를 해결한다.

∙ 3단계 결합(Combine) 분할해서 해결한 결과를 결합하여 마무리한다

2. 분할 방법

3. 재귀적 구현 (최소단위 까지 분할)

간단한 정렬 알고리즘

1. 버블 정렬

- 버블 정렬의 이해

- 소스 코드

- 성능 평가

* 비교 횟수 : 두 데이터간의 비교연산 횟수

* 이동 횟수 : 위치의 변경을 위한 데이터의 이동 횟수

-> 실제로 시간 복잡도에 대한 빅-오(O)를 결정하는 기준은 '비교 횟수'이다. 하지만, 이동 횟수에 관한 성능까지 체크 한다면 동일 한 빅-오 연산에 대한 세밀한 성능평가가 가능하다.

- 비교 횟수 : O(n^2)

- 이동 횟수

-> 정렬이 되어 있는 경우 : 한번도 이동이 발생 하지 않음

-> 역순으로 정렬 되어 있는 경우 : O(n^2) 

(실제론 비교 횟수의 3배 소요)

2. 선택 정렬

- 선택 정렬의 이해

- 소스 코드

void SelSort(int arr[], int n) { int i, j; int maxIdx; int temp; for(i=0; i<n-1; i++) { maxIdx = i; // 정렬 순서상 가장 앞서는 데이터의 index for(j=i+1; j<n; j++) // 최소값 탐색 { if(arr[j] < arr[maxIdx]) maxIdx = j; } /* 교환 */ temp = arr[i]; arr[i] = arr[maxIdx]; arr[maxIdx] = temp; } } int main(void) { int arr[4] = {3, 4, 2, 1}; int i; SelSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

- 성능 평가

- 비교 횟수 : O(n^2)

- 이동 횟수 : O(n) Worst Case와 Best Case관계 없이 동일

3. 삽입 정렬

- 삽입 정렬의 이해

- 소스 코드

void InserSort(int arr[], int n) { int i, j; int insData; for(i=1; i<n; i++) { insData = arr[i]; // 정렬 대상을 insData에 저장 for(j=i-1; j>=0 ; j--) { if(arr[j] > insData) arr[j+1] = arr[j]; // 비교 대상 한 칸 뒤로 밀기 else break; // 삽입 위치 찾았으니 탈출! } arr[j+1] = insData; // 찾은 위치에 정렬 대상 삽입! } } int main(void) { int arr[5] = {5, 3, 2, 4, 1}; int i; InserSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<5; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

- 성능 평가

- 비교 횟수 : O(n^2)

- 이동 횟수 : 

Worst Case -> O(n^2)

Best Case -> 한번도 발생 안함