삽입 정렬

• 앞에서부터 해당 원소가 위치 할 곳을 탐색하고 해당 위치에 삽입

입력 리스트 : (7, 3, 2, 8, 9, 4, 6, 1, 5)

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)

2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.

3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

삽입 정렬 분석

• 한번의 탐색 시간 복잡도 : O(i)
• 총 연산 시간 : O(n2)
• 리스트가 부분적으로 정렬되어 있을 때 좋음. 작은 n에 대해 가장 좋은 정렬 방법

구현

public class Main {

    public static void main(String[] args) {
        int[] arr = {7, 3, 2, 8, 9, 4, 6, 1, 5};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            for (int i = end; i > 0; i--) {
                if (arr[i - 1] > arr[i])
                    swap(arr, i - 1, i);
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

---

reference

• 고려대학교 김상곤 교수님 강의 중
• 자바 [JAVA] - 삽입 정렬 (Insertion Sort)
• [알고리즘] 삽입 정렬 - Insertion Sort (Python, Java)