[C언어] 삽입정렬(insertion sort)

삽입정렬: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘

 

#include <stdio.h>

int main() {
	int arr[] = {10, 20, 15, 1}; // int형 배열 선언
	int i, j, key;

	for (i = 1; i < 4; i++) {
		key = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > key) { // 앞 배열 값과 현재 배열 값 비교
			arr[j + 1] = arr[j];
			j--; 
		}
		arr[j + 1] = key;
	}

	for (int k = 0; k < 4; k++) {
		printf("%d ", arr[k]);
	}
	printf("\n");
}

 

1. int형 arr 배열 선언

---

2. i = 1

key = 20(arr[1])

j = 0

 

while ( 0 >= 0 && 10 > 20) => X

arr[1] = 20

 

-. 변화 없음.

---

3. i = 2

key = 1 (arr[2])

j = 1

 

while (1 >= 0 && 20 > 1) => O

arr[2] = 20 (arr[1])

j = 0

 

-. while 조건에 맞음. arr[2] 값이 1에서 20으로 바뀜. 즉, arr[2]값에 arr[1] 값을 넣음.

-. j 값은 0

 

---

while(0 >= 0 && 10 > 1) => O

arr[1] = 10 (arr[0])

j = -1

 

-. while 조건에 맞음. arr[1]의 값이 20에서 10으로 바뀜. 즉, arr[1]값에 arr[0]값을 넣음.

-. j 값은 -1

---

while (-1 >= 0 && arr[-1] > 1) => X

 

arr[0] = 1(key)

-. while 조건에 안 맞음. while문 빠져나옴.

-. arr[0] 값은 10에서 1로 바뀜. 즉, arr[0] 값에 key 값을 넣음. key 값은 1임.

---

4. i = 4

key = 15

j = 2

while (2 >= 0 && 20 > 15) => 0

arr[3] = 20 (arr[2])

j = 1

-. while 조건에 맞음. arr[3] 값에 arr[20] 값인 20을 넣음.

 

---

while (1 >= 0 &&  10 > 15) => X

arr[2] = 15

 

-. while 조건에 안맞음. while 빠져나옴. 

-. arr[j+1]에 key값을 넣음. 즉, arr[2]에 key값 15를 넣음. 

---

-. 즉 최종적으로 {10, 20, 1, 15} 배열값이 {1, 10, 15, 20}으로 바뀜.