InsertionSort.md

삽입 정렬이란?

앞에서부터 차례대로 이미 정렬된 부분과 비교해 자신의 위치를 찾아냄으로써 정렬

핵심 개념

정렬할 자료를 두 개의 부분 집합 S, U로 가정
부분집합 S : Sorted, 정렬된 앞 부분 원소
부분집합 U : UnSorted, 아직 정렬되지 않은 나머지 원소들

이때, 반드시 S는 U보다 앞에 위치해야 함

---

정렬 과정

1. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내, 이미 정렬된 부분집합 S의 마지막 원소부터 비교하며 위치 찾아 삽입
2. 삽입 정렬을 반복하며 부분집합 S의 원소는 하나씩 늘리고, 부분집합 U의 원소는 하나씩 감소
3. 부분집합 U가 공집합이 되면 삽입 정렬 종료

왜 마지막 원소부터 비교할까?

반드시는 아니지만 특정 케이스에서 연산 횟수를 줄일 수 있는 장점이 있기 때문에

어떤 케이스?

• 입력 데이터가 이미 오름차순으로 정렬되어 있는 상황

---

시간 복잡도

1. 평균, 최악

• O(N^2)
• 원소 N, 비교 횟수 N

2. 최선

• O(N)
• 원소 N, 비교 횟수 1

→ 버블정렬, 선택정렬의 경우 이미 데이터가 오름차순이더라도 모든 경우를 다 확인하기 때문에 O(N^2)임

---

적절한 활용

• 이미 정렬된 데이터가 있고, 새로 데이터가 추가될 때
• 데이터의 개수가 적을 때 (다만, 이 경우는 어떤 알고리즘이든 유리함)

---

구현

import java.util.*;

public class InsertionSort {
    public static void main(String[] args) {
        int[] data = {69, 10, 30, 2, 7, 16, 8, 31, 22};

        // 정렬되지 않은 집합(U) 원소 하나씩 순회
        // 처음 정렬된 집합(S)는 0번 인덱스만 존재, 따라서 1번 인덱스 부터 순회
        for(int i=1; i<data.length; i++) {
            int key = data[i];
            // 정렬된 집합(S)의 뒤에서부터 비교하며 위치 찾기
            int j;
            for(j=i-1; j>=0 && data[j]>key; j--) {
                data[j+1] = data[j];
            }
            // 반복문 안에서 key가 들어갈 위치 찾았는데..
            data[j+1] = key;
        }
        System.out.println(Arrays.toString(data));
    }
}

첫 번째 사이클
S = {69}
U = {10, 30, 2, 7, 16, 8, 31, 22}
data = {69, 10, 30, 2, 7, 16, 8, 31, 22}
key = 10

반복문 실행중 ...
j = 0 ---> data = {69, 69, 30, 2, 7, 16, 8, 31, 22}
반복문 종료
data = {10, 69, 30, 2, 7, 16, 8, 31, 22}

======================================

두 번째 사이클
S = {10, 69}
U = {30, 2, 7, 16, 8, 31, 22}
data = {10, 69, 30, 2, 7, 16, 8, 31, 22}
key = 30

반복문 실행중 ...
j = 1 ---> data = {10, 69, 69, 2, 7, 16, 8, 31, 22}
j = 0 ---> data = {10, 69, 69, 2, 7, 16, 8, 31, 22}
반복문 종료
data = {10, 30, 69, 2, 7, 16, 8, 31, 22}

---

관련 문제

백준 24051 : 알고리즘 수업 - 삽입 정렬 1