[알고리즘] 삽입 정렬 (Insertion Sort)

1. 삽입 정렬 (insertion sort)

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

자세히 보기 https://visualgo.net/en/sorting

 

 

삽입 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다.


이전에 다뤘던 선택 정렬과는 달리 삽입 정렬은 '안정 정렬' 이다.

[장점]
1. 추가적인 메모리 소비가 적다.
2. 거의 정렬된 경우 매우 효율적이다. 즉, 최선의 경우 O(N)의 시간복잡도를 갖는다.
3. 안정 정렬이 가능하다.


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

2. 자바로 알고리즘 구현

1. for(int index = 0; index < 100; index++)로 반복
2. 반복문 안에서, for (int index2 = index + 1; index2 > 0; index2--)으로 반복

• 내부 반복문 안에서 if(dataList.get(index2) < dataList.get(index2-1)) 이면, 스왑

import java.util.ArrayList;
import java.util.Collections;

public class InsertionSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        for (int index = 0; index < dataList.size() - 1; index++) {
            for (int index2 = index + 1; index2 > 0; index2--) {
                if (dataList.get(index2) < dataList.get(index2 - 1)) {
                    Collections.swap(dataList, index2, index2 - 1);
                } else {
                    break;
                }
            }
        }
        return dataList;
    }
}

 

3. 정리

 

삽입 정렬의 경우 거의 정렬된 배열에서 좋은 성능을 보이기 때문에 실제로 병합정렬과 삽입 정렬을 혼합한 Tim Sort(팀 정렬)이 있다. 또한 이 팀 정렬이 프로그래밍 언어에서도 자체 라이브러리로 정렬 알고리즘에 적용하고 있는 언어들이 있다.
Tim Sort는 이진 삽입 정렬이기 때문에 삽입 정렬에 대한 메커니즘은 확실하게 이해하고 있어야 한다.

 

 

 

이번 삽입 정렬은 매우 기초적인 정렬 방법 중 하나다. 이후 필자가 목표했던 Tim Sort와 Dual-pivot Quick Sort을 다루기 전에 기본 정렬 방식을 확실히 알아야 한다.

 

 

 

 

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