삽입 정렬(Insertion Sort)

1. 정의 🧵

삽입 정렬

  삽입 정렬은 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
  카드 예시를 살펴보면 쉽게 이해할 수 있을 것이다. '4, 2, 3, 1, 5'라는 숫자 적힌 5장의 카드가 순서대로 있다고 하자. 앞에서부터 순서대로 카드를 뽑으면서 손에 쥔다고 생각하자. 뽑힌 카드는 이미 손에 쥐어진 카드들 사이에 위치를 찾아들어간다.

이미 손에 쥐어져 있는 카드들	뽑은 카드	자신의 위치를 찾아들어간 모습
	4	4
4	2	2  4
2  4	3	2  3  4
2  3  4	1	1  2  3  4
1  2  3  4	5	1  2  3  4  5

  1번 숫자가 적힌 카드가 자신의 위치를 찾아가는 것을 다시 한번 살펴보자. 1번 카드는 4번과 비교하고, 3번과 비교하고, 2번과 비교하여 자신의 위치에 도달하게 된다. 그러면 1번과 비교하여 더 큰 값을 가진 카드들은 한 칸씩 뒤로 밀리게 된다. 이와 같은 방식으로 나머지 카드들도 자신의 위치를 찾아들어가게 된다.

 

2. 동작 방식 🧶

  위의 카드 예시를 잘 이해했다면 동작 방식은 매우 간단하다.

1. 자리를 찾아가야 하는 i번째 원소를 지정한다.
2. (i - 1) 번째 원소부터 i번째 원소와 비교를 시작한다.
3. i번째 원소보다 큰 경우에는 자신의 자리에서 한 자리씩 뒤로 밀리게 된다.
4. 비교되는 원소가 i번째 원소보다 작은 경우에 비교를 멈춘다.
5. 밀리지 않은 원소들과 밀린 원소들의 사이에 i번째 원소가 위치하게 된다.

 

3. 구현(JAVA) 🧣

void insertionSort(int[] arr) {
    for(int idx = 1; idx < arr.length; idx++) {
        int temp = arr[idx];
        int compareIdx = idx - 1;

        while((compareIdx >= 0) && (temp < arr[compareIdx])) {

            arr[compareIdx + 1] = arr[compareIdx];
            compareIdx--;
        }

        // 밀리지 않은 원소들과 밀린 원소들 사이에 해당 원소가 위치한다.
        arr[compareIdx + 1] = temp;
    }
}

 

4. 시간복잡도 & 공간복잡도 📐

1. 시간복잡도

  역으로 정렬이 되어 있는 경우(최악의 경우) i번째 원소마다 (i - 1) 번 비교를 해야 한다. 원소가 N개가 있는 경우 아래와 같은 연산이 수행된다.

1 + 2 + ... + (N - 2) + (N - 1) = N * (N - 1) / 2

  따라서, 최악의 경우 시간복잡도는 O(N ^ 2)이다.

  만약 정렬이 되어 있는 경우(최선의 경우)에는 i번째 원소마다 1번만 연산을 수행하면 되므로 O(N)의 시간복잡도를 가진다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N)	O(N^2)	O(N^2)

2. 공간복잡도

공간복잡도의 경우 추가적인 배열을 만들지 않고 해당 배열에서 교환이 이루어지므로 O(N)이다.

 

5. 장점 & 단점 💡

1. 장점

• 코드가 매우 단순하다.
• 다른 메모리 공간을 필요로 하지 않는다.
• 정렬이 되어 있는 경우 매우 효과적이다. - O(N)의 시간복잡도
• 앞에서 살펴본 버블 정렬과 선택 정렬에 비해 상대적으로 빠르다.

2. 단점

• 최악의 경우 시간복잡도가 O(N^2)이므로 상당히 비효율적이다.
• 배열의 길이가 긴 경우 비효율적이다.

 

해당 글은 Gyoogle님의 삽입 정렬(Insertion Sort)을 참고하였습니다.