[정렬] 삽입정렬

 

삽입정렬

원리

삽입 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)

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

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

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

코드

최선 시간복잡도: O(n)

최악 시간복잡도: O(n²)

    //최적: N, 최악:N제곱
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int key = arr[i];   // 현재 삽입할 원소
            int j = i - 1;

            // key보다 큰 원소들을 한 칸씩 뒤로 밀기
            //내림차순
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            //오름차순
//            while (j>=0 && arr[j]>key){
//                arr[j+1] = arr[j];
//                j--;
//            }

            // 올바른 위치에 key 삽입
            arr[j + 1] = key;
        }
    }

 

궁금증

🔹 왜 arr[j + 1]인가?

• while 루프에서 j를 하나 줄일 때마다 값을 오른쪽으로 한 칸씩 밀기 때문에, 마지막으로 멈췄을 때 j는 key가 들어갈 자리보다 하나 앞을 가리키고 있습니다.
• 그래서 key는 j + 1 위치에 넣어야 정확히 들어갑니다.
• while 루프가 끝나면 j값이 음수값이 되어있기때문에 `+1`을 해줘야 한다.

 

장점

1. 추가적인 메모리 소비가 작다.
2. 거의 정렬 된 경우 매우 효율적이다. 즉, 최선의 경우 O(N)의 시간복잡도를 갖는다.
3. 안정정렬이 가능하다.(주위 근접 데이터를 비교해가기 때문)

단점

1. 역순에 가까울 수록 매우 비효율적이다. 즉, 최악의 경우 O(N2)의 시간 복잡도를 갖는다.
2. 데이터의 상태에 따라서 성능 편차가 매우 크다.

출처:

https://st-lab.tistory.com/179