[Sort]간단한 정렬 알고리즘

간단한 정렬 알고리즘

1. 버블 정렬

- 버블 정렬의 이해

- 소스 코드

void BubbleSort(int arr[], int n) { int i, j; int temp; for(i=0; i<n-1; i++) { for(j=0; j<(n-i)-1; j++) { if(arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int main(void) { int arr[4] = {3, 2, 4, 1}; int i; BubbleSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

- 성능 평가

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

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

-> 실제로 시간 복잡도에 대한 빅-오(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 -> 한번도 발생 안함