[알고리즘] 삽입 정렬

삽입 정렬(Insertion sort)

리스트를 왼쪽부터 차례대로 보면서

현재 요소를 그 앞쪽의 정렬된 구간에 적절한 위치에 '삽입'하는 방식

즉 하나씩 꺼내서 앞에서부터 위치를 찾아 넣는 방식이라서 삽입 정렬이라고 불립니다.

 

과정

1. 두 번째 요소부터 시작해요. 이 값을 key라고 부를게요.
2. key의 왼쪽에 있는 값들을 하나씩 거꾸로 보면서
   key보다 큰 값이 있다면 한 칸씩 뒤로 밀어요.
3. 이렇게 하다 보면 key보다 작거나 같은 값을 만나게 되는데
   그 바로 뒤에 key를 넣으면 돼요.
4. 이 과정을 리스트 끝까지 반복하면 정렬이 완료됩니다.

 

동작 과정 예시

정렬할 리스트: `[5, 3, 4, 1, 2]`

 

1. `i = 1`, 3은 5보다 작다 → swap → `[3, 5, 4, 1, 2]`
2. `i = 2`, 4는 5보다 작다 → swap → `[3, 4, 5, 1, 2]`
   → 4는 3보다 크므로 멈춤
3. `i = 3`, 1은 5보다 작다 → swap
   → 1 < 4 → swap
   → 1 < 3 → swap → `[1, 3, 4, 5, 2]`
4. `i = 4`, 2는 5보다 작다 → swap
   → 2 < 4 → swap
   → 2 < 3 → swap → `[1, 2, 3, 4, 5]` 정렬 완료!

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

알고리즘 구현

public static List<Integer> insertionSort(List<Integer> dataList) {
    int n = dataList.size();

    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0; j--) {
            if (dataList.get(j) < dataList.get(j - 1)) {
                // swap
                int temp = dataList.get(j);
                dataList.set(j, dataList.get(j - 1));
                dataList.set(j - 1, temp);
            } else {
                break;
            }
        }
    }

    return dataList;
}

 

+) 다른 방식으로 구현

Live Programming Mode - Python Tutor - Visualize Python and JavaScript code

 

알고리즘 분석

• 이중 반복문 `O(n^2)`
• 최악의 경우 `n*(n-1)/2`
• 완전 정렬이 되어 있는 경우(최선) `O(n)`