[알고리즘] 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)

삽입하기 적절한 위치를 찾으면 그 위치에 삽입을 하되, 원래 있던 숫자들은 뒤로 한칸씩 민 후, 아이템을 추가한다.

 

1) 입력

17

14

11

19

13

15

 

2) 절차

i = 1

i 위치의 값을 앞 부분의 적당한 위치에 끼워 넣는다.

17	14	11	19	13	15
14	17	11	19	13	15

 

i = 2

14	17	11	19	13	15
11	14	17	19	13	15

 

i = 3

11

14

17

19

13

15

 

i = 4

11	14	17	19	13	15
11	13	14	17	19	15

 

i = 5

11	13	14	17	19	15
11	13	14	15	17	19

 

 

3) 요약

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int value = a[i];
	// a 배열의 0 에서 i-1 사이에서 value 보다 큰 값들을
	// 뒤로 한 칸씩 이동하고, 그 값들 앞에 value를 넣는다.
    }
}