삽입 정렬 알고리즘

선택한 원소의 앞이 정렬된 배열로 간주하고 그 배열에 원소를 삽입해 나아가는 정렬 알고리즘이다.

 

0 회전 : [ 8, 4, 10, 1 ]  ◀ 초기 배열 

• key = 4
• arr [0]은 이미 정렬되어 있다고 간주한다.

1 회전 : [ 4, 8, 10, 1 ]  

•   [ 8, 4, 10, 1 ]   →  [ 8, 8, 10, 1 ]
•   [ 8, 8, 10, 1 ]   →  [ 8, 8, 10, 1 ]

2 회전 : [ 4, 8, 10, 1 ]

•  [ 4, 8, 10, 1 ]   →  [ 4, 8, 10, 1 ]

3 회전 : [ 1, 4, 8, 10 ]  ◀ 정렬 완료

•  [ 4, 8, 10, 1 ]   →  [ 4, 8, 10, 10 ]
•  [ 4, 8, 10, 10 ]   →  [ 4, 8, 8, 10 ]
•  [ 4, 8, 8, 10 ]   →  [ 4, 4, 8, 10 ]
•  [ 4, 4, 8, 10 ]   →   [ 1, 4, 8, 10 ]

 

Code

#include <stdio.h>

void insertSort(int arr[], int length) {
	int j, temp;
	for (int i = 1; i < length; i++) {
		temp = arr[i];
		for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
			arr[j + 1] = arr[j];
		}
		// j = -1 or arr[j] <=arr[i]
		arr[j + 1] = temp;
	}
}

int main() {
	// 변수선언
	int arr[] = { 7, 5, 1, 2, 10, 8, 3 };

	// 실행
	//insertSort(arr, 7);
	insertSort(arr, 7);
	// 결과 출력
	printf("정렬된 결과: [");


	for (int i = 0; i < 7; i++) {
		printf("%d ", arr[i]);
		printf(" ");
	}

	printf("]");
	return 0;
}