[정렬] Insertion Sort(삽입 정렬)

1. 삽입 정렬(Insertion Sort) 정리

삽입 정렬은 배열의 앞부분은 항상 정렬되어 있다고 가정하고, 새로운 값을 적절한 위치에 삽입하여 정렬을 완성하는 방식이다.

초보자도 이해하기 쉬운 정렬 알고리즘 중 하나이며, 특히 거의 정렬되어 있는 배열에서는 빠른 성능을 보인다.

---

2. 삽입 정렬의 동작 원리

1. 두 번째 원소부터 시작하여, 현재 원소를 앞의 정렬된 부분과 비교한다.
2. 자기보다 큰 값을 만날 때까지 뒤로 한 칸씩 밀고 자리를 만든다.
3. 알맞은 자리에 현재 값을 삽입한다.

---

3. 코드 구현

삽입 정렬 함수

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

        // 중간 결과 출력
        System.out.println(i + "회차 정렬 결과 :" + Arrays.toString(arr));
    }
}

메인 함수 예시

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {7, 9, 10, 8, 6};

        Sort.insertSort(arr, arr.length);
        System.out.print("정렬 결과 : " + Arrays.toString(arr));
    }
}

Sort.insertSort로 호출하도록 클래스명 확인 필요!

---

4. 실행 결과 예시

1회차 정렬 결과 :[7, 9, 10, 8, 6]
2회차 정렬 결과 :[7, 9, 10, 8, 6]
3회차 정렬 결과 :[7, 8, 9, 10, 6]
4회차 정렬 결과 :[6, 7, 8, 9, 10]
정렬 결과 : [6, 7, 8, 9, 10]

---

5. 시간 및 공간 복잡도

• 최선의 경우 (이미 정렬된 경우): O(n)
• 평균 / 최악의 경우: O(n²)
• 공간 복잡도: O(1) (추가 메모리 없이 제자리 정렬)

---

6. 특징 요약

항목	내용
정렬 방식	비교 기반, 제자리 정렬
안정 정렬 여부	안정 정렬 (같은 값의 원소가 정렬 후에도 원래의 순서를 유지함)
시간 복잡도	O(n²)
공간 복잡도	O(1)
장점	구현 간단, 거의 정렬된 데이터에 강함
단점	데이터 양이 많으면 느림

 

---

💡 Tip: 삽입 정렬은 소규모 데이터나 부분 정렬된 데이터에 유용하며, 다른 정렬 알고리즘의 일부로 활용되기도 한다!