[sort]삽입 정렬(Insertion sort)

1학기 자료구조 수업을 더 열심히 들을 걸..이라는 생각을 했다

개인공부이므로 오류가 있을 수 있습니다!

 

1. 정의

삽입 정렬은 무작위로 나열되어 있는 데이터를 오름차순으로 정리하는 정렬의 방법 중 하나이다.

나열 되어 있는 데이터의 원소를 적절한 위치에 삽입하여 정렬한다

 

2. 코드

위와 같은 내용을 코드로 구현하면 다음과 같다.

#include <stdio.h>

int main() {
	int i, j, temp;
	int arr[10] = { 1,11, 55, 7, 8, 10, 63, 3, 97, 9 };

	for (i = 0; i < 9; i++) {
		j = i; //삽입할 원소를 지정한다
		while (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
			j--; //삽입될 원소의 정확한 위치를 찾기 위해 인덱스 번호를 한칸씩 줄이며 계속 비교 
		}
	}

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

자료 배열의 모든 요소를 앞에서부터 차례로 정렬된 배열 부분과 비교하여 삽입될 원소의 위치를 찾기 때문에 버블정렬이나 선택 정렬보다는 효과적이다