삽입 정렬(Insertion Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

삽입 정렬(Insertion Sort)

 

 

 

1. 삽입 정렬이란?

삽입 정렬은 정렬되지 않은 데이터를 하나씩 가져와 이미 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘입니다. 간단한 구현과 적은 데이터에서는 높은 성능을 보이는 정렬 방식입니다.

---

 

 

2. 원리

1. 배열의 두 번째 요소부터 시작하여 해당 요소를 정렬된 부분에 삽입합니다.
2. 이전 요소들과 비교하며 적절한 위치를 찾습니다.
3. 모든 요소가 정렬될 때까지 반복합니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [5, 3, 8, 4, 2]

1. 첫 번째 단계:
   • 두 번째 요소 3을 정렬된 부분 [5]에 삽입합니다.
   • 3은 5보다 작으므로 앞에 삽입합니다.
   • 결과: [3, 5, 8, 4, 2]
2. 두 번째 단계:
   • 세 번째 요소 8을 정렬된 부분 [3, 5]에 삽입합니다.
   • 8은 이미 가장 크므로 그대로 둡니다.
   • 결과: [3, 5, 8, 4, 2]
3. 세 번째 단계:
   • 네 번째 요소 4를 정렬된 부분 [3, 5, 8]에 삽입합니다.
   • 4는 5와 8 사이에 삽입됩니다.
   • 결과: [3, 4, 5, 8, 2]
4. 네 번째 단계:
   • 다섯 번째 요소 2를 정렬된 부분 [3, 4, 5, 8]에 삽입합니다.
   • 2는 가장 앞에 삽입됩니다.
   • 결과: [2, 3, 4, 5, 8]

최종 정렬 결과: [2, 3, 4, 5, 8]

반응형

---

 

 

4. 시간 복잡도

• 최선의 경우: O(n) (데이터가 이미 정렬되어 있는 경우)
• 평균적인 경우: O(n²)
• 최악의 경우: O(n²) (데이터가 역순으로 정렬된 경우)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

Java 코드

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};

        insertionSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

Python 코드

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [5, 3, 8, 4, 2]
insertion_sort(arr)
print(arr)

---

 

 

6. 주의점

1. 데이터 크기가 커질수록 성능이 저하되므로, 소규모 데이터에 적합합니다.
2. 안정 정렬이므로 동일한 값의 순서가 유지됩니다.

---

 

 

7. 장단점

장점

• 구현이 간단하고 이해하기 쉬움.
• 데이터가 거의 정렬되어 있는 경우 빠르게 동작함.
• 안정 정렬로, 동일한 값의 순서가 유지됨.

단점

• 시간 복잡도가 O(n²)로 비효율적.
• 대규모 데이터에는 적합하지 않음.

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주