정렬 - 선택정렬, 삽입정렬

선택정렬(Selection Sort)과 삽입정렬(Insertion Sort)은 기본적인 정렬 알고리즘입니다. 어떻게 동작하는지 정확하게 파악하고 특징을 알아둔다면 많은 알고리즘 문제에서 유용하게 쓰일 수 있습니다. 앞서 포스팅한 ‘소소한팁’도 이 둘을 이용한 팁입니다. 예를 들어서 이미 정렬되어 있는 배열에 새로운 값을 넣어야 하는 경우 삽입정렬을 사용하면 어려운 알고리즘 사용 없이 Time Complexitiy: N 에 넣을 수 있습니다. 혹은 정렬되지 않은 매우 큰(N) 배열에서 맨 앞에 일부만(M) 정렬해야 할 때 선택정렬을 사용하면 Time Complexity: NM 에 정렬할 수 있습니다.

선택정렬과 삽입정렬

#include <stdio.h>

int main() {

	// Selection Sort
	int arr1[10] = { 5,4,2,1,8,3,0,6,9,7 };
	int total_num_1 = 10;
	for (int i = 0; i < total_num_1 - 1; i++) {
		int cur = arr1[i];
		int cur_idx = i;
		for (int j = i + 1; j < total_num_1; j++) {
			if (cur > arr1[j]) {
				cur = arr1[j];
				cur_idx = j;
			}
		}
		int temp = arr1[cur_idx];
		arr1[cur_idx] = arr1[i];
		arr1[i] = temp;
	}

	for (int i = 0; i < total_num_1; i++) {
		printf("%d ", arr1[i]);
	}
	printf("\n");


	// Insertion Sort
	int arr2[10] = { 5,4,2,1,8,3,0,6,9,7 };
	int total_num_2 = 10;
	for (int i = 1; i < total_num_2; i++) {
		int k = arr2[i];
		int j = i - 1;
		for (; j >= 0; j--) {
			if (arr2[j] > k) {
				arr2[j + 1] = arr2[j];
			} else {
				break;
			}
		}
		arr2[j + 1] = k;
	}

	for (int i = 0; i < total_num_2; i++) {
		printf("%d ", arr2[i]);
	}
	printf("\n");

}

출력

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9