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

알고리즘을 이해하자 하자 하자 하자!

---

 

함께 보면 좋을 포스팅

[알고리즘] 선택 정렬(Selection Sort)

---

 

삽입 정렬의 이해

삽입 정렬은 두 번째 원소부터 지정을 시작해 그 앞 인덱스의 원소들과 비교하여
지정한 원소의 정확한 정렬 위치를 판단한 후, 원소를 삽입해 정렬하는 방식입니다.

원소가 들어갈 정확한 위치를 판단하는 과정에서 그 앞 인덱스의 원소들은 그 위치가 점차 뒤로 옮겨집니다.

 

방식

삽입 정렬은 크게 4단계로 동작합니다.

1. 지정 : 정렬 위치를 판단할 원소를 지정합니다. (두 번째 원소부터 시작)
2. 비교 : 지정한 원소의 앞 인덱스들과 그 값을 비교합니다.
   1. 조건이 충족된 원소(지정 원소보다 작거나 큰 경우)는 한 인덱스씩 뒤로 순서를 옮깁니다.
   2. 조건이 충족되지 않은 원소의 인덱스에서 비교를 중단하며, 해당 인덱스를 저장합니다.
3. 삽입 : 2단계에서 비교를 중단한 후 '저장한 인덱스의 바로 뒤에' 1단계에서 지정한 원소를 삽입합니다.
4. 회전 : 지정 인덱스를 증가시킵니다. 회전을 원소의 마지막 배열인 n까지 반복합니다.

 

분류

삽입 정렬은 정렬 유형 3가지 에 해당합니다.

• 비교 정렬 : 정렬 연산이 두 값을 비교하는 것을 기반으로 일어납니다.
• 제자리 정렬 : 주어진 메모리 공간 외에 추가적인 공간을 필요로 하지 않는 정렬 방식
  • 원소의 정렬이 내부적으로 이뤄지며, 원소 외부의 필요한 변수나 메모리가 거의 없음을 의미함
• 안정 정렬 : 입력 순서와 동일하게 정렬 (중복 원소 존재 시 원소의 순서를 보장합니다)

 

 

삽입 정렬의 구현

알고리즘 내부 동작 흐름

삽입 정렬을 활용해 배열 `{3, 9, 1, 7, 5}` 를 `오름차순` `{1, 3, 5, 7, 9}`로 정렬할 시 내부 원소의 정렬 흐름 예시입니다.

 

 

[범례]

* 현재 지정한 원소 : `i`

* 지정 원소와 비교할 원소 : `j`

* 비교가 중단된 원소 (지정 원소가 삽입될 위치의 바로 앞)

 

 

[알고리즘 동작 단계 : 총 4단계]

1. 지정 : 정렬된 위치를 판단할 원소를 지정합니다. (두 번째 원소부터 시작)
   1. 예제에서는 지정 인덱스를 `i` 를 통해 지정합니다. 지정한 원소 값은 `arr [i]`이며, 이 값은 임시 변수에 저장합니다.
2. 비교 : 지정한 원소의 앞 인덱스들과 그 값을 비교합니다.
   • 조건이 충족된 원소(지정 원소보다 작거나 큰 경우)는 한 인덱스씩 뒤로 순서를 옮깁니다.
     • 예제에서는 비교하는 원소의 인덱스를 `j` 를 통해 탐색, 비교합니다. 탐색하는 원소 값은 `arr [j]`입니다.
     • arr [j]가 조건을 만족할 시 원소가 `arr [j+1]` 위치로 이동합니다. (뒤로 밀림)
   • 조건이 충족되지 않은 원소의 인덱스에서 비교를 중단하며, 해당 인덱스를 저장합니다.
     • 비교가 중단된 인덱스 j를 저장합니다.
3. 삽입 : 2단계에서 비교를 중단한 후 '저장한 인덱스의 바로 뒤'에 1단계에서 지정한 원소를 삽입합니다.
   1. 1단계에서 임시 변수에 저장했던 `arr [i]` 를 인덱스 `j + 1` 로 삽입합니다. (해당 원소의 최종 정렬 위치)
4. 회전 : 지정 인덱스를 증가시킵니다. 회전을 원소의 마지막 배열인 n까지 반복합니다. ( i 가 증가됩니다)

 

3	9	1	7	5

비교 원소 : 9 (임시 변수에 저장)

 

1. 두 번째 인덱스부터 지정을 시작하며 지정된 i = 1의 원소인 9 가 들어갈 위치를 탐색합니다.

2. 오름차순 정렬이므로 지정한 원소보다 앞의 원소가 작은 경우를 만날 때까지 탐색, 비교합니다.

 

3	9	1	7	5

비교 원소 : 9 (임시 변수에 저장)

 

3. 현재 경우에는 비교하는 원소인 3 이 9 보다 작기 때문에으로 탐색이 종료되며,

9가 삽입될 위치는 탐색이 종료된 3 (i = 0)의 바로 뒤인 i = 1입니다.

삽입되는 위치가 현재 위치와 같으므로 순서 변화는 일어나지 않습니다.

 

3	9	1	7	5

비교 원소 : 1 (임시 변수에 저장)

 

4. 지정 인덱스를 증가시킵니다. 지정 인덱스를 i = 2 , 지정 원소는 1로 변경되었습니다.

5. 지정 인덱스의 바로 앞 원소부터 0의 인덱스까지 탐색, 비교를 시작합니다.

 

3	9	9	7	5

비교 원소 : 1 (임시 변수에 저장)

 

6. 9 가 1 보다 크므로 9의 위치를 한 칸 뒤로 이동시킵니다.

 

3	9	9	7	5

비교 원소 : 1 (임시 변수에 저장)

 

7. 다음으로 9의 앞의 인덱스 원소인 3을 1과 비교해 줍니다.

3 또한 1 보다 크므로 3의 위치를 한 칸 뒤로 이동시킵니다.

 

3	3	9	7	5

비교 원소 : 1 (임시 변수에 저장)

 

8. 비교 원소의 앞 인덱스를 대상으로 비교, 탐색이 종료되었습니다.

비교 원소인 1보다 작은 원소가 없으므로, 1은 자연적으로 맨 앞 인덱스로 삽입됩니다.

 

1	3	9	7	5

비교 원소 : 1 → 삽입 위치 j = -1의 뒤

 

9. 2회전이 완료되었습니다.

이하의 처리 과정은 위와 동일하므로 정렬이 동작하는 순서를 도표를 통해 참고하시기 바랍니다.

 

1	3	9	7	5

비교 원소 : 7 (임시 변수에 저장)

 

1	3	9	7	5

비교 원소 : 7 (임시 변수에 저장)

 

1	3	9	9	5

비교 원소 : 7 (임시 변수에 저장)

 

1	3	9	9	5

비교 원소 : 7 (임시 변수에 저장)

 

1	3	7	9	5

비교 원소 : 7 → 삽입 위치 j = 1(원소 3)의 뒤

 

1	3	7	9	5

비교 원소 : 5 (임시 변수에 저장)

 

1	3	7	9	5

비교 원소 : 5 (임시 변수에 저장)

 

1

3

7

9

9

비교 원소 : 5 (임시 변수에 저장)

 

1	3	7	9	9

비교 원소 : 5 (임시 변수에 저장)

 

1	3	7	7	9

비교 원소 : 5 (임시 변수에 저장)

 

1	3	7	7	9

비교 원소 : 5 (임시 변수에 저장)

 

1	3	5	7	9

비교 원소 : 5 → 삽입 위치 j = 1(원소 3) 의 뒤

 

1	3	5	7	9

 

회전 및 정렬이 완료되었습니다. 

 

 

슈도 코드

method sort(배열의 길이, 정렬할 배열) { // 배열을 오름차순으로 정렬한다.
    for (삽입할 원소를 지정하는 인덱스 i : 2번째 원소 ~ 배열 끝까지 1씩 증가 loop){
        임시 변수 = arr[i] 저장
        for (지정 원소와 비교할 원소를 순회할 인덱스 j : i-1부터 0까지 1씩 감소 loop){
            if (arr[j] > 지정 원소) 
                arr[j]를 arr[j+1]로 이동
            else if(지정 원소보다 작은 수를 만날 시) break;
        }
        // j loop 종료 후(탐색 종료 후)
        arr[j+1] = 지정 원소(임시 변수)
    }
    return arr;
}

 

구현 (java)

public int[] solution(int n, int[] arr) { // 배열을 오름차순으로 정렬한다.
    for (int i = 1; i < n; i++){
        int tmp = arr[i], j;
        for (j = i-1; j >= 0; j--){
            if (arr[j] > tmp) arr[j+1] = arr[j];
            else break;
        }
        arr[j+1] = tmp;
    }
    return arr;
}

 

시간복잡도

• 최선(정렬되어 있는 경우) : 비교 1번, 외부 loop n-1
• 최악(역순 정렬인 경우) : 비교 n-1번 + n -2 번 ... + 2 번 ... 1 번 = `n(n-1) / 2`, 교환은 각 루프마다 `i + 2` 번 발생
  • `비교` `n(n-1) / 2` `*` `교환` `2(n-1), Worst T(n)` = O(n^2)
• 시간복잡도 :
  • 최선 : T(n) = O(n)
  • 평균 : T(n) = O(n^2)
  • 최악 : T(n) = (n^2)

 

결론

• 삽입 정렬 알고리즘의 장점
  • 이해와 구현이 매우 편합니다.
  • 선택 정렬이나 거품 정렬보다는 빠릅니다.
  • 정렬을 시행하는 원소가 비교적 정렬되어 있는 경우는 효율적일 수 있습니다.
• 삽입 정렬 알고리즘의 단점
  • 원소의 교환 수가 많기 때문에 배열의 크기가 커지면 비효율적입니다.

 

# 구현 코드

클릭 시 깃허브로 연결됩니다.