기본 정렬 - 삽입 정렬 (insertion sort)

1. 삽입 정렬(Insertion sort)

: 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번쨰와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

2. 예제

- 배열에 7, 4, 2, 6, 1 이 저장되어있다고 가정 -> 오름차순 정렬

 

1회전 :

2회전 :

3회전 :

4회전 :

결과 :

3. Java 삽입정렬 예제

import java.util.Arrays;

public class insertionSort {
 
    public static void main(String[] args) {
       
        int[] data = { 9, 6, 3, 5, 1 };
     
        for(int i = 1; i < data.length; i++){       
            int key = data[i];
            int j = 0;
            for(j = i - 1; j >= 0; j--){
                if(data[j] > key){ 	
                    data[j + 1] = data[j];                
                }else{
                    break;
                }              
            }
            data[j + 1] = key; 
            
        System.out.println(Arrays.toString(data));
    	}
    }
}

 

4. 시간 복잡도

데이터의 개수를 n개라고 가정한다면,

(n -1) + (n - 2) + ... + 2 + 1 => n(n - 1)/2이 되므로, O(n^2)만큼의 시간이 걸린다. 

하지만 삽입 정렬은 모두 정렬이 되어있는 경우에는 한 번씩만 비교를 하게 되므로 O(n)의 시간복잡도를 가지게 된다.