[C언어] 삽입 정렬 구현 프로그램

삽입정렬이란?

정렬되어 있는 부분집합(S)에 정렬할 원소의 위치를 찾아 삽입하는 방식으로 정렬을 수행한다.

 

특징

1. 정렬할 자료가 2개의 부분집합 S(Sorted Subset)와 U(Unsorted Subset)으로 나누어져있다.

2. 제일 앞부분 원소부터 정렬을 수행한다.

   (정렬된 앞부분의 원소의 부분집합이 S, 정렬되지 않은 원소의 부분집합은 U가 된다.)

3. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 S의 마지막 원소부터 비교하면서 삽입한다.

4. 실행을 한번할때마다 S의 원소는 하나씩 늘고 U의 원소는 하나씩 줄어든다.

  (이후, U가 공집합이 되면 실행이 종료된다.)

---

예시

 

실행 예시

(한번 실행될때마다 S의 부분집합이 한개씩 늘어나는 모습이다)

---

#include <stdio.h>
#define Size 8

void insertionSort(int a[]) {
	int i, j, temp;
	printf("\n 정렬할 원소는 : ");
	for (int t = 0; t < Size; t++) {
		printf("%3d", a[t]);
	}

	printf("\n\n <<삽입 연산 수행>> \n");
	//i=0이 아닌 이유는 비교연산을 i=1부터하기 때문이다
	for (i = 1; i < Size; i++) { 
		temp = a[i]; //a[1],a[2],a[3]....
		j = i;
		//j는 1이상이어야한다 && 비교대상이 더 큰 경우
		while ((j > 0) && (a[j - 1] > temp)) {
			a[j] = a[j - 1];
			j--;
		}
		//temp가 들어갈 자리를 찾은후 a[j]에 temp를 넣어준다
		a[j] = temp;
		printf("\n %d 단계: ", i);
		for (int t = 0; t < Size; t++) {
			printf("%3d", a[t]);
		}
	}
}

void main() {
	int list[Size] = { 69,10,30,2,16,8,31,22 };

	insertionSort(list);
}