[알고리즘] 삽입 정렬(INSERT SORT) : 개념과 자바 예제 코드

삽입 정렬이란?

삽입 정렬은 "하나씩 살펴보고, 알맞은 위치에 끼워 넣는다"는 방식으로 동작해요.
📌 쉽게 말하면:

• 카드 놀이를 할 때, 손에 든 카드들을 작은 숫자부터 정렬한다고 상상해 보세요.
• 이미 정렬된 카드 사이에 새로운 카드를 끼워 넣는 것처럼 작동해요.

---

작동 과정 🎯

1. 두 번째 원소부터 시작합니다(첫 번째 원소는 이미 정렬된 상태로 간주).
2. 현재 위치의 숫자를 왼쪽으로 비교하면서 적절한 위치를 찾습니다.
3. 숫자를 옮기며 자리를 마련하고, 찾은 위치에 삽입합니다.
4. 이 과정을 배열 끝까지 반복하면 정렬이 완료됩니다. 😊

---

자바(Java) 코드 예제 ☕

public class InsertionSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 4, 6, 2, 9}; // 정렬할 배열

        // 삽입 정렬 알고리즘
        for (int i = 1; i < numbers.length; i++) {
            int current = numbers[i]; // 현재 삽입할 숫자
            int j = i - 1;

            // 현재 숫자를 올바른 위치에 삽입하기 위해 뒤로 이동
            while (j >= 0 && numbers[j] > current) {
                numbers[j + 1] = numbers[j]; // 오른쪽으로 숫자 이동
                j--;
            }
            numbers[j + 1] = current; // 현재 숫자를 제자리에 삽입

            // 중간 과정 출력
            System.out.print("Step " + i + ": ");
            for (int num : numbers) {
                System.out.print(num + " ");
            }
            System.out.println(); // 한 단계 끝난 후 줄바꿈
        }

        // 최종 결과 출력
        System.out.print("Sorted Array: ");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

---

출력 결과 🖨️

Step 1: 4 8 6 2 9
Step 2: 4 6 8 2 9
Step 3: 2 4 6 8 9
Step 4: 2 4 6 8 9
Sorted Array: 2 4 6 8 9

---

코드 동작 설명

1. 배열 {8, 4, 6, 2, 9}를 정렬합니다.
2. 두 번째 원소 4가 첫 번째 원소 8보다 작으므로 자리를 바꿉니다.
3. 다음으로 6을 정렬된 부분과 비교하며 적절한 위치에 삽입합니다.
4. 이 과정을 반복하면 배열이 완전히 정렬됩니다. 🥳

---

파이썬(Python) 코드 예제 🐍

def insertion_sort(numbers):
    for i in range(1, len(numbers)):  # 두 번째 원소부터 시작
        current = numbers[i]  # 현재 삽입할 숫자
        j = i - 1

        # 현재 숫자를 올바른 위치에 삽입하기 위해 뒤로 이동
        while j >= 0 and numbers[j] > current:
            numbers[j + 1] = numbers[j]  # 숫자를 오른쪽으로 이동
            j -= 1
        numbers[j + 1] = current  # 현재 숫자를 제자리에 삽입

        # 중간 과정 출력
        print(f"Step {i}: {numbers}")

    return numbers

# 정렬할 숫자 리스트
numbers = [8, 4, 6, 2, 9]
print("Original Array:", numbers)
sorted_numbers = insertion_sort(numbers)
print("Sorted Array:", sorted_numbers)

---

출력 결과 🖨️

Original Array: [8, 4, 6, 2, 9]
Step 1: [4, 8, 6, 2, 9]
Step 2: [4, 6, 8, 2, 9]
Step 3: [2, 4, 6, 8, 9]
Step 4: [2, 4, 6, 8, 9]
Sorted Array: [2, 4, 6, 8, 9]

---

코드 동작 설명

1. 리스트 [8, 4, 6, 2, 9]를 입력받습니다.
2. 두 번째 숫자 4부터 정렬 시작, 이전 숫자 8과 비교하여 올바른 위치에 삽입합니다.
3. 나머지 숫자들도 같은 방식으로 정렬된 위치에 삽입됩니다.
4. 최종적으로 [2, 4, 6, 8, 9]가 출력됩니다. 🐾

---

왜 삽입 정렬을 배울까?

• 간단한 원리: 초보자가 배우기 쉬워요.
• 작은 데이터에서 빠름: 데이터가 적을 때는 효율적이에요.
• 실제 카드 놀이와 비슷: 이해하기에 친숙한 예로 설명 가능해요.

정렬 알고리즘을 처음 접하는 분들에게 삽입 정렬은 훌륭한 출발점이에요! 😊

2024.12.14 - [자료구조 및 알고리즘] - 병합 정렬 (Merge Sort) 쉽게 이해하기 : 예시 코드

병합 정렬 (Merge Sort) 쉽게 이해하기 : 예시 코드

2024.12.14 - [자료구조 및 알고리즘] - 퀵 정렬 (Quick Sort) 쉽게 이해하기 : 예시 코드

퀵 정렬 (Quick Sort) 쉽게 이해하기 : 예시 코드