3. 삽입 정렬(Insertion Sort)

 

이번에는 삽입정렬에 대해 알아봅시다.

전에 알아본 두 가지 정렬 알고리즘인 선택정렬, 버블 정렬은 시간복잡도가 O(N^2) 로, 비효율적이었습니다.

 

문제는 동일합니다.

다음 숫자들을 오름차순으로 정렬하시오.
1  10  5  8  7  6  4  3  2  9

 

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방식으로 문제를 해결합니다.

선택, 버블 정렬은 모든 원소를 돌면서 정렬은 했지만 삽입 정렬은 그렇지 않고 필요한 경우에만 위치를 바꿉니다.

 

 

소스코드

public class TestMain {
    public static void main(String[] args) {
        int[] array = {1,10,5,8,7,6,4,3,2,9};
        for(int i=0;i<9;i++){
            int j=i;
            while(j>=0 && array[j]>array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                j--;
            }
        }

        for(int i:array){
            System.out.print(i+" ");
        }
    }
}

삽입 정렬의 특이한 점은 시간복잡도가 O(N^2)로 비효율적이지만,

정렬이 어느정도 완료된 배열에서는 아주 빠른 모습을 보인다는 것입니다. 정렬이 완벽하게 된 배열에서는 O(1) 까지도 가능합니다.

즉 거의 정렬이 완료된 배열에서는 어느 알고리즘보다도 빠르다는 특징을 가지고 있습니다.

 

다음 숫자 리스트를 오름차순으로 정렬해 봅시다.

1  2  4  5  6  7  8  9  10  11 12 13 14 15 3

 

이 경우 거의 정렬이 완료가 되어있습니다.

이 경우 삽입 정렬이 앞에서 설명한 2개의 정렬 알고리즘보다 연산 횟수가 월등히 적습니다.