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

  삽입 정렬(Insertion Sort)이란 앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식입니다. 알고리즘 복잡도는 O(n^2)입니다. 앞의 원소부터 정렬하면서 비교하는 원소보다 클 경우에 비교를 중단하므로 버블 정렬보다는 빠른 편입니다.

 

정렬되지 않은 데이터

15

11

1

3

8

↓

11

15

1

3

8

↓

1

11

15

3

8

↓

1

3

11

15

8

↓

정렬이 끝난 데이터

1

3

8

11

15

 

  삽입 정렬 구현 코드

pubilc class Main {
	public static void insertionSort(int[] array) {
    	for (int i = 1; i < array.length; i++) {
        	for (int j = i; j > 0; j--) {
            	if (array[j] < array[j - 1]) {
            		int temp = array[j];
                	array[j] = array[j - 1];
                	array[j - 1] = temp;
            	} else {
                	break;
            }
        }
    }
}

  바깥 for문이 1부터 array의 길이만큼 순회합니다.

  안쪽 for문이 j는 i번째부터 j가 0보다 큰 동안 j가 1씩 감소합니다.

  if문에서 array의 j번째 원소가 array의 j - 1번째 원소보다 크다면 두 원소의 위치를 바꿔야 합니다.  임시 변수 temp를 생성하고 array의 j번째 원소를 할당합니다.  array의 j번째 원소에 array의 j - 1번째 원소를 할당합니다.  array의 j - 1번째 원소에는 array의 j번째 원소를 할당했던 임시 변수 temp를 할당합니다.

 

  예제 출처: 컴퓨터 개론(자세한 설명이 필요하다면 아래 주소로)

  https://terms.naver.com/entry.naver?docId=2270436&cid=51173&categoryId=51173&expCategoryId=51173