🔍 삽입 정렬이란?

삽입 정렬(Insertion Sort)은 데이터를 순차적으로 확인하며,
이미 정렬된 앞부분과 비교하고 올바른 위치에 삽입해가는 방식입니다

📌삽입 정렬의 동작 방식

실제 예시를 통해 선택 정렬의 동작방식을 살펴보겠습니다
예를 들어, [5, 3, 4, 1, 2] 배열을 오름차순으로 정렬할 것입니다

첫 번째 원소(5)는 이미 정렬된 상태라고 보고 두 번째 원소부터 비교를 시작합니다

🎈 1회차 비교 과정:

• 두 번째 원소(3)를 첫 번째 원소인 5와 비교합니다
• 3이 5보다 작기 때문에, 3을 5의 앞으로 이동시킵니다 → [3, 5, 4, 1, 2]

🎈 2회차 비교 과정:

• 세 번째 원소(4)를 두 번째 원소인 5와 비교합니다
• 4가 5보다 작으므로, 다시 앞의 3과 비교합니다
• 4는 3보다 크기 때문에, 3과 5 사이에 삽입됩니다 → [3, 4, 5, 1, 2]

🎈 3회차 비교 과정:

• 네 번째 원소(1)를 세 번째 원소 5와 비교합니다
• 1은 5보다 작아 다시 앞의 4, 그리고 3과 차례로 비교합니다
• 1이 지금까지 비교한 모든 숫자보다 작기 때문에 맨 앞에 삽입됩니다 → [1, 3, 4, 5, 2]

🎈 4회차 비교 과정:

• 다섯 번째 원소(2)를 네 번째 원소 5와 비교합니다
• 2가 5보다 작아서 앞의 원소들과 계속 비교를 진행합니다 (4, 3, 1)
• 1보다는 크므로, 1 다음 자리에 들어갑니다 → [1, 2, 3, 4, 5]

이제 모든 숫자가 오름차순으로 정렬되었습니다 ([1, 2, 3, 4, 5])

🚀 실제 코드로 구현하기

위에서 설명한 동작 방식을 코드로 구현하면 다음과 같습니다

int[] arr = {5, 3, 4, 1, 2};  
for (int i = 1; i < arr.length; i++) {  
    int tmp = arr[i];  
    int idx = i-1;  
    while(idx >= 0 && tmp < arr[idx]) {  
        arr[idx+1] = arr[idx];  
        idx--;  
    }  
    arr[idx+1] = tmp;  
}

이 코드를 실행하면 배열은 [1, 2, 3, 4, 5]의 형태로 오름차순 정렬됩니다

🛠️ 시간복잡도

• 최선의 경우(이미 정렬된 상태): O(n)
• 최악의 경우(역순으로 정렬된 상태): O(n²)
• 평균적인 경우: **O(n²)

📌 장점

• 추가적인 메모리가 필요 없는 In-place 정렬 방식입니다

📌 단점

• 성능이 나쁩니다 (시간복잡도: O(n²))

✨ 삽입 정렬이 안정 정렬인 이유

삽입 정렬은 앞에서부터 원소를 하나씩 뽑아서 이미 정렬된 부분과 비교하며 위치를 결정합니다
이 과정에서 만약 같은 값이 나오더라도 뒤에 있던 원소가 기존의 원소 앞을 넘어가지 않고,
바로 뒤에 삽입되기 때문에 원래의 상대적인 순서가 유지됩니다

즉, 삽입 정렬은 같은 값의 데이터끼리 원래 순서를 절대로 뒤집지 않기 때문에 안정 정렬입니다

예시를 들어 설명하면,

원본 배열: [5, 3(1), 3(2), 1]
여기서 두 번째 원소 3(1)와 세 번째 원소 3(2)가 같은 값이라 정의하겠습니다

삽입정렬 알고리즘을 적용해 오름차순 정렬하면 배열은 아래와 같이 됩니다

• 정렬 후 배열: [1, 3(1), 3(2), 5]

같은 값인 3(1)와 3(2)의 순서가 변하지 않았다는 걸 알 수 있습니다
따라서 삽입 정렬은 안정 정렬입니다

✍️ 결론

삽입 정렬은 데이터를 순차적으로 확인하며,
이미 정렬된 앞부분과 비교하고 올바른 위치에 삽입해가는 정렬 방식입니다

별도의 추가 공간 없이 배열 내에서 정렬(In-place)이 가능하다는 장점이 있지만,
시간 복잡도가 좋지 않다는 단점도 존재합니다