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

1. 개념

선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘

2. 과정

1. 아직 정렬하지 않은 부분에서 첫 번째 요소를 선택한다.
2. 이웃한 왼쪽 요소의 값이 선택한 값보다 크면 왼쪽 요소의 값을 오른쪽으로 옮기고, 이 작업을 선택한 값보다 작은 요소를 만날 때까지 반복한다.
3. 정렬이 끝날 때까지 1~2를 반복한다.
   

3. 구현

void insertionSort(int[] arr, int n) {
	for(int i=1; i<n; i++) {	// 1.
    	int j;
    	int temp = arr[i];
        for(int j=i; j>0 && arr[j-1] > temp; j--) {	// 2.
        	arr[j] = arr[j-1];
        }
        arr[j] = temp;	// 3.
    }
}

1. 배열의 첫 번째 요소(arr[0])는 정렬이 된 상태로 가정하므로 두 번째 요소부터 정렬을 시작한다. 변수 temp에 현재 선택한 값(arr[i])을 저장해놓는다.
2. 선택한 값과 왼쪽의 요소들을 비교하기 위해, 인덱스의 값은 현재 위치부터 시작해 한 자리씩 감소한다(j--). 왼쪽 요소의 index 값은 선택값의 인덱스 - 1이므로, 왼쪽 요소의 인덱스 값이 음수가 나오지 않도록 j>0 이라는 조건을 걸어준다. 왼쪽 요소의 값(arr[j-1])이 선택값(temp)보다 크다면 왼쪽 요소를 오른쪽으로 한 자리 이동시켜준다. 계속 왼쪽으로 이동하며 이 과정을 반복하다가, 선택값보다 작은 값이 등장하면 반복문을 종료한다.
3. 선택값이 있어야 할 자리를 찾은 상태이므로, 현재 위치의 값(arr[j])에 저장해놓았던 선택값(temp)을 삽입한다.

4. 성능 분석

for(int i=1; i<n; i++) {
    int j;
    int temp = arr[i];
    for(int j=i; j>0 && arr[j-1] > temp; j--) {
        arr[j] = arr[j-1];
    }
    arr[j] = temp;
}

바깥 루프 i	안쪽 루프 j에서의 비교 횟수
i=0	n-1
i=1	n-2
i=2	n-3
...	...
i=(n-2)	1

• 총 비교 횟수 = 안쪽 루프 j에서의 비교 횟수의 합
  (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2
  ∴ 시간복잡도 O(n^2)

• 역순으로 정렬된 경우(최악) → O(n^2)
  50 40 30 20 10
40 50 30 20 10 => 1
  30 40 50 20 10 => 2
  20 30 40 50 10 => 3
  10 20 30 40 50 => 4

• 원하는 순서대로 이미 정렬되어 있는 경우(최선) => O(n)
  10 20 30 40 50
10 20 30 40 50 => 1
  10 20 30 40 50 => 1
  10 20 30 40 50 => 1
  10 20 30 40 50 => 1

5. 특징

• 입력이 거의 정렬된 경우 다른 어떤 정렬 알고리즘보다 빠른 수행 시간 O(n)을 가진다.
• 안정적 정렬 알고리즘이다.
• 제자리 정렬 알고리즘이다.
• 삽입될 위치를 찾기 위해 한 번에 한 자리씩만 이동하므로 데이터의 이동이 여러 번 발생하게 되는데, 데이터의 이동이 많아질 경우 속도가 느려지게 되어 비효율적이다.

---

📖 참고

• Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱
• 이관용. "알고리즘 10강. 정렬 알고리즘 (1)" 방송통신대학교, 2022년.