[JAVA] Insertion Sort (삽입정렬)

1. Insertion Sort 개념

아래와 같은 순서로 카드가 놓여져 있다고 생각해보자.

4

5

3

2

(1)

4

5

3

2

2번째부터 기준이 되어 시작한다. (왼쪽과 비교해야 하므로 2번째부터 시작한다)

기준인 5와 그 왼쪽인 4를 비교하니 5가 더 크므로 냅둔다.

4

5

3

2

이 알고리즘은 특성상, 기준의 왼쪽 값들은 모두 정렬이 되어있다.

(2)

4

5

3

2

그 다음 기준은 3번째가 되었다.

바로 왼쪽 값과 비교한다.

3이 5보다 작기에, 큰 값인 5를 기준 자리에 밀어 넣는다.

(여기서 회색부분은 비어있는 자리라고 생각하면 됨)

4

5

2

3

이번엔 기준과, 그 왼쪽인 4와 비교한다.

기준값이 4보다 작으므로, 위에서처럼 4를 오른쪽으로 밀어 넣는다.

4

5

2

이제 비교대상이 없어졌으므로 비어있는 자리에는 기준값이 들어간다.

3

4

5

2

(3)

3

4

5

2

기준값은 4번째가 되었다.

바로 왼쪽 값과 비교한다.

2가 5보다 작기에, 큰 값인 5를 기준자리로 밀어 넣는다.

3

4

5

2

이번에도 마찬가지로 기준값과 그 왼쪽인 4를 비교한다.

기준값보다 4가 더 크므로, 오른쪽으로 보내버린다.

3

4

5

2

기준과 왼쪽 값인 3을 비교한다. 

이번에도 3이 더 크므로, 오른쪽으로 보낸다.

3

4

5

마지막으로 빈곳에 기준 값을 넣으면 정렬이 완료된다.

2

3

4

5

2. 예제

public class InsertionSort { public static void main(String[] args) { int [] arr = {10, 2, 6, 4, 3, 7, 5}; for (int i = 1; i < arr.length; i++) { int standard = arr[i];  // 기준 int aux = i - 1;   // 비교할 대상 while (aux >= 0 && standard < arr[aux]) { arr[aux + 1] = arr[aux];   // 비교대상이 큰 경우 오른쪽으로 밀어냄 aux--; } arr[aux + 1] = standard;  // 기준값 저장 } printArr(arr); } public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

결과 >>

2 3 4 5 6 7 10