정렬 알고리즘(3. 삽입정렬)

삽입 정렬

1. 개념

평균	최악	메모리	안정성
$O(N^2)$	$O(N^2)$	$O(1)$	O

삽입 정렬은 말 그대로 Insertion(넣다) 해당하는 장소에 넣는 정렬입니다.
특정 범위 내에서 해당 요소가 들어갈 자리에 쏙! 넣는다 라고 생각하면 이해하기 쉽습니다.

삽입 정렬은 현재 위치의 요소를 뽑아 이전 방문했던 요소들 중 어디 사이에 넣어야 정렬이 유지되는지 판단하는 정렬 방식입니다.

매 순회마다 해당 요소를 이전 요소들 사이 어딘가에 넣게 되는데 이 경우 이후 요소들을 한자리씩 밀어내야하기때문에 구현하기가 꽤 까다롭습니다.

2. 동작 과정

int[] arr = new int[]{7,4,2,5,6};

1. 기준 인덱스(1)부터 이전 범위에서 해당 값이 들어갈 위치 찾기
2. 해당 위치로 요소 삽입
3. 기준 인덱스 위치 증가
4. 인덱스를 순차적으로 증가시키며 해당 과정 반복

→ 해당 과정을 1회 통과마다 살펴봐야하는 범위가 1씩 증가합니다.

3. 삽입 정렬의 시간 복잡도

삽입 정렬은 총 N-1회의 반복을 진행합니다.
순회를 하며 살펴보는 요소의 수는 N-1 → N-2 → ... 1 로 줄어들게 되는데 모든 항이 평균적으로 $\frac{N}{2}$ 만큼 살펴보게 됩니다.
또, 원본 배열을 가지고 정렬을 진행하기때문에 별도의 메모리 소요는 없기때문에 공간복잡도는 $O(1)$이 됩니다.

이를 정리해보면 아래와 같습니다.

• 총 반복 횟수: N-1
• 평균 살펴보는 요소 수: $\frac{N}{2}$
• 시간 복잡도: $O(\frac{N(N-1)}{2}) ⇒ O(N^2)$
• 공간복잡도: $O(1)$
• 안정성: O

구현

1. swap 방식 한꺼번에 요소를 밀기보다는 인접한 요소 비교하며 해당 위치 찾아가는 방식

void insertionSort(int[] arr) {
    int len = arr.length;

        for(int i = 1; i < len; i++){
            int target = arr[i];

            // swap을 통해 위치 이동
            for(int j = i-1; j >=0; j--){
                if(target < arr[j]){
                    arr[j+1] = arr[j];
                    arr[j] = target;
                    target = arr[j];
                }else{
                    break;
            }
        }
    }
}

2. shift 방식 위치를 찾은 뒤 한번에 요소 이동 후 삽입

void insertionSort(int[] arr) {
    int len = arr.length;
        for (int i = 1; i < len; i++) {
            int target = arr[i];
            int j = i - 1;

            // target보다 큰 원소들은 오른쪽으로 한 칸씩 이동
            while (j >= 0 && arr[j] > target) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 찾은 위치에 target 삽입
            arr[j + 1] = target;
        }
}