[알고리즘] 삽입 정렬 (Insertion Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도)

목차

• 삽입 정렬이란?
• 삽입 정렬 과정
• 삽입 정렬 구현 (자바 코드)
• 시간복잡도
• 공간복잡도
• 정렬 알고리즘 비교

 

---

1. 삽입 정렬이란?

선택한 요소를 이미 정렬된 요소들과 비교해 알맞은 위치에 삽입한다. 선택한 요소의 앞쪽 요소들은 이미 정렬된 상태를 유지하고 있으므로, 매 순서마다 바로 이전 인덱스 요소와 비교하여 원소가 삽입될 올바른 위치를 찾아낸다.

 

(특징)

• 최선의 시간복잡도는 O(n)이며, 평균 및 최악의 시간복잡도는 O(n^2)이다.
• O(n^2)의 시간복잡도를 가지는 선택 정렬과 버블 정렬에 비해 상대적으로 속도가 빠르다.

 

(장점)

• 알고리즘이 단순하고, 구현이 쉽다.
• 이미 정렬된 배열일 경우, 매번 1번의 비교로 정렬되기 때문에 O(n)의 시간복잡도를 가지며 매우 효율적이다.
• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.

(단점)

• 다른 정렬 알고리즘에 비해 비교적 많은 교환이 발생한다.
• 배열의 길이가 길어질수록 지수적으로 시간이 증가하기 때문에 비효율적이다.

 

---

2. 삽입 정렬 과정

1) 두번째 요소부터 선택하여 진행한다.

 

2) 앞쪽 요소와 비교하며 삽입할 위치를 찾는다.

 

    2-1) 2번째 요소는 1번째 요소와 비교한다.

    2-2) 3번째 요소는 2번째 요소와 비교한다.

    2-3) 3번째 요소는 1번째 요소와 비교한다.

    2-4) 4번째 요소는 3번째 요소와 비교한다.

                                ...

    2-k) n번째 요소는 1번째 요소와 비교한다.

 

3) 삽입할 위치를 찾았다면, 해당 위치의 값을 뒤로 옮기고 선택했던 값을 삽입한다.

 

4) 정렬되지 않는 값들에 대해 (1)번 과정부터 다시 반복한다.

 

https://www.geeksforgeeks.org/java-program-for-insertion-sort/

 

---

3. 삽입 정렬 구현 (자바 코드)

import java.util.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        int[] arr = {5, 2, 2, 9, 100, 70, 11};
        int n = arr.length;

        // 오름차순 정렬
        int tmp;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (arr[j] > arr[j+1]) {
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
                else break;
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

 

---

4. 시간복잡도

데이터의 개수가 n일 때,

• 두번째 인덱스에서 비교 횟수 : 1 => 1번
• 세번째 인덱스에서 비교 횟수 : 1 ~ 2 => 2번
• 네번째 인덱스에서 비교 횟수 : 1 ~ 3 => 3번
  ...
• n번째 인덱스에서 비교 횟수 : 1 ~ n-1 => n-1번

 

최선의 경우,

1 + 1 + .. + 1 = n 이다.

따라서 O(n)의 시간복잡도를 가진다.

 

최악의 경우,

1 + 2 + .. + n-2 + n-1 = n * (n-1) / 2 이다.

따라서 O(n^2)의 시간복잡도를 가진다.

 

---

5. 공간복잡도

데이터의 개수가 n일 때,

 

주어진 배열 내에서 교환이 이뤄지므로 공간복잡도는 O(n)이다.

 

---

6. 정렬 알고리즘 비교 (시간복잡도)