삽입 정렬(Insertion sort)

목차

1. 삽입 정렬이란?
2. 사용 예시
3. 장점과 단점

1. 삽입 정렬이란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입함으로 완성하는 알고리즘입니다.
내림차순으로 정렬해야 하는 경우 다음과 같은 코드로 나타낼 수 있습니다.

int n = v.length();
for (int i = 1; i < n; i++){
	
    int key = v[i];
    for (int j = i -1; j >= 0 && v[j] < key ; j--) {
    	
        v[j + 1] = v[j];
    }
    v[j + 1] = key;
}

2. 사용 예시

위에 주어진 배열을 내림차순으로 정렬하겠습니다.
i = 1일 때 다음과 같은 과정을 거칩니다.

j 는 i - 1부터 0까지 혹은 key값보다 큰 수가 나올 때까지 j의 값을 낮춥니다.
현제 i가 1이기때문에 j의 값은 0만을 확인합니다.
v[0]의 값은 42로 key값 68 보다 작기 때문에 j는 0까지 작아집니다.
또한 j의 값을 낮추면서 v[j + 1]는 v[j]의 값을 가지기 때문에 지금 v[1]는 42가 됩니다.
또한 i의 값을 늘리기 전에 v[j]의 값을 key로 자장합니다.
현제 j는 0이므로 v[0]는 68이 됩니다.
위와 같은 과정을 i가 n - 1이 될 때까지 반복합니다.

i가 3(n - 1)이 될 때까지 진행하면 내림차순으로 정렬된 것을 확인할 수 있습니다.

3. 장점과 단점

전체적으로 앞서 설명드렸던 버블 정렬과 동일합니다.

3-1. 장점

구현 난이도가 낮습니다.

3-2. 단점

다른 알고리즘에 비해 시간 복잡도가 큽니다.