[알고리즘 - 정렬] 선택 정렬 vs 삽입 정렬

1. 선택 정렬

: 가장 작은 숫자를 찾아서 정렬되지 않은 구간의 맨 처음으로 옮긴다.

c언어 code

#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void selection_sort(int arr[], int n) {
	int i, j, least, temp;  //least : 정렬되지 않은 것 중에서 가장 작은 숫자
	for (i = 0; i < n; i++) {
		least = i;
		for (j = i+1; j < n; j++) {
			if (arr[least] > arr[j]) {
				least = j;
			}
		}
		SWAP(arr[i], arr[least], temp);
	}
}

 

2. 삽입정렬

: 정렬되지 않은 요소 하나를 정렬된 구간에 어디에 넣을지 정하는 정렬

key = '정렬되지 않은 요소'  (즉, 정렬된 구간에 '삽입'할 요소)

정렬된 구간 뒤에서부터 key와 비교하면서 앞으로 한칸씩 이동한다.

 

정렬된 구간 뒤에서부터 순회하는 것이 좀 까먹기 쉬운데 이유는 간단하게 비어있는 key자리로 한칸씩 이동하기 편하기 때문!

c언어 code

//정렬 안된 요소를 어디에 배치할 지 정하는 정렬 == 삽입정렬

void insertion_sort(int arr[], int n) {
	int i, j, key;
	for (i = 1; i < n; i++) { 
		key = arr[i];    //정렬되지 않은 요소
		for (j = i-1; j >= 0 && arr[i] > key; j--) {  //정렬된 구간(뒤에서부터 접근)
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = key;
	}
}