6-4. 단순 삽입 정렬(Straight Insertion Sort)

단순 삽입 정렬

• 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복해 정렬하는 알고리즘
• 단순 선택 정렬과 비슷하지만, 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다름
• 셔틀 정렬(shuttle sort)이라고도 함

 

 

 

2번째 요소부터 선택해 진행

 

 

4는 6보다 작으므로 6보다 앞쪽에 삽입, 그 다음에는 3번째 요소 1을 선택해 앞쪽에 삽입

 

 

 

아직 정렬되지 않은 부분의 첫 번재 요소를 정렬된 부분의 알맞은 위치에 삽입

위와 같은 작업을 n - 1회 반복하면 정렬을 마침

 

 

 

 

 

[알고리즘 개요]

for(int i = 1; i < n; i++) {
	//tmp <- a[i]
    	//a[0], ..., a[i - 1]의 알맞은 공간에 tmp를 삽입
}

 

 

 

배열의 요소를 알맞은 위치에 삽입

• tmp에 a[i]를 대입
• 반복 제어용 변수 j에는 i - 1을 대입
• 아래의 두 조건 중 하나를 만족할 때까지 j를 1씩 감소하면서 대입하는 작업 반복

1. 정렬된 열의 왼쪽 끝에 도달
2. tmp보다 작거나 같은 key를 갖는 항목 a[j]를 발견

 

 

이때 드모르간 법칙을 적용하면 아래의 두 조건이 모두 성립할 때까지 반복

1. j가 0보다 큼
2. a[j - 1] 값이 tmp보다 큼

 

 

이 과정을 마친 뒤 요소 a[j]에 tmp를 대입하면 한 요소에 대한 단순 삽입 정렬 종료

 

 

 

 

 

[실습 코드]

static void insertionSort(int[] a, int n) {
        for(int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            for(j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

 

 

 

 

 

단순 정렬의 시간 복잡도

• 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬의 시간 복잡도는 모두 O(n2)
• 효율이 좋은 편은 아님