[정렬] 선택 vs 버블 vs 삽입

정렬의 종류

- 교환(Exchange) : 버블(Bubble), 퀵(Quick) 정렬

- 삽입(Insertion) : 삽입(Intsertion), 셀(Shell) 정렬

- 병합(Merging) : 2-way 병합, n-way 병합

- 분배(Distribution) : 기수(Radix) 정렬

- 선택(Selection) : 선택(Selection), 힙(Heap) 정렬

선택정렬(Selection Sort)

전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환(Exchange)하는 정렬 방식이다.

- STEP.1

- STEP.2

- STEP.3

- STEP.4

• 특성 : 평균 시간복잡도 O(n^2)으로 느린 알고리즘이다. 하지만 최악의 경우도 O(n^2)으로 평균(최선)과 동일하다.정렬의 안정성^[각주:1]을 만족하지 않는다.

버블정렬(Bubble Sort)

전체 자료들들 대상으로 인접한 두 개의 자료값을 비교하여 교환(Exchange)하는 정렬 방식이다.

- STEP.2

- STEP.2

• 특성 : 평균 시간복잡도는 O(n^2)이며 최선의 경우(정렬된 경우 자료의 이동 연산이 0회 발생) O(0)이다. 자료의 정렬 상태에 따라 이동 연산의 차이가 있고 정렬의 안정성이 유지된다.

삽입정렬(Insertion Sort)

정렬된 부분 집합에 정렬할 자료의 위치를 찾아 삽입(Insertion)하는 정렬 방식이다.

- STEP.1

- STEP.2

• 특성 : 자료의 정렬 상태에 따라 시간복잡도가 매우 크게 차이난다. 정렬이 되어있다면 삽입위치를 찾을 때 1번만 비교하고 이동연산이 없다. 따라서 최선의 경우 O(n)의 시간복잡도를 갖는다. 평균 시간복잡도는 O(n^2)이며 정렬의 안정성은 유지된다.

소스코드

void selection_sort(int arr[], int n) { int min, temp; for(int i=0; i<n-1; i++) // 전체 자료의 개수보다 1번 작게 돈다.(Swap의 횟수) { min = i; // 자료값으로 접근하지 말고 인덱스로 접근해야 Swap시 유용 for(int j=i+1; j<n; j++) // 선택된 위치의 다음 위치부터 마지막까지 탐색 if(arr[j] < arr[min]) min = j; // 최소값 갱신 // Swap temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } void bubble_sort(int arr[], int n) { int temp; for(int i=0; i<n-1; i++) // 전체 자료의 개수보다 1번 작게 돈다. { for(int j=0; j<n-i-1; j++) if(arr[j] > arr[j+1]) { // Swap temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } void insertion_sort(int arr[], int n) { int key, i, j; for(i=1; i<n; i++) // i가 삽입할 원소의 인덱스가 된다. { key = arr[i]; for(j=i-1; j>=0; j--) // 삽입할 원소의 아래 인덱스부터 내려가며 삽입위치를 찾는다. { if(arr[j] > key) // 삽입 위치가 아니라면 현재 탐색위치의 값을 이전 탐색위치에 대입 arr[j+1] = arr[j]; else break; } arr[j+1] = key; } }

1. 정렬의 안정성 : 동일한 키 값을 갖는 레코드들의 상대적인 우치가 정렬 후에도 바뀌지 않는 것을 말한다. [본문으로]