InsertionSort(삽입정렬)이란?

Insertion Sort?

- 가장 기본적인 정렬방법 중(Bubble Sort, Selection Sort)와 같이 시간복잡도 O(N^2)를 가진다.

- 안정적인 정렬 방법이다.

- 최선의 경우 O(N), 최악의 경우 O(N^2)이다.

- N의 크기가 작을수록 O(N^2)의 정렬 방법이 효율이 좋다

 

* Why ? 

- Quick, Merge의 경우 Function Call 에 들어가는 비용이 더 커지므로!

시간복잡도에 대한 고찰

- 최선의 경우 : 주어진 key값에 대하여 한번만 비교하고 끝날 때!!!! ( 땡기는 작업 X )

- 최악의 경우 : 주어진 key값에 대하여 모든 원소를 비교해야 할 때!!

정렬 순서

1. 0번째 index는 제외하고, 1번째부터 index를 시작한다!

2. 해당 범위내에 마지막 Index를 key값으로 지정한다!

3. 해당 key값 보다 작은값이 나올때 까지 한칸씩 앞으로 땡긴다!

4. 이러한 과정을 마지막 index까지 진행하면 된다!

1. 5를 기준 key값으로 지정한다!

2. 44는 5보다 크므로 한칸 땡긴다

3. 38도 5보다 크므로 한칸씩 땡긴다

4. 3은 5보다 작으므로 여기선 끝!

구현

소스 원문

package study;
 
import java.util.Arrays;
 
/**
 * 기초 정렬 방법중의 하나인 Insertion Sort를 구현한다
 * 이 정렬 방법이 살아남은 이유는
 * 최선의 경우가 O(N)이고, 메모리를 덜 잡아먹는 특징 때문이다!
 * 물론 최악은 O(N^2)이지만, N이 작을 때는 효율적이다
 * 분할 정복의 경우, 함수를 호출하는 과정 때문에 작은 값의 데이터에는
 * 배보다 배꼽이 더 커버리게 되는데
 * 이때는 Insertion Sort를 이용하면 성능이 개선된다!
 * 10,000 개 데이터 정렬시 걸리는 시간 : 25ms
 * 100,000 개 데이터 정렬시 걸리는 시간 : 2216ms ( 데이터 분포에 따라 시간은 바뀜 )
 * @author huisam
 *
 */
public class InsertionSort {
    
    private static int SIZE = 100000;
    
    /** 배열을 저장할 변수 */
    private int arr[] = new int[SIZE];
    
    /** 객체 생성시 난수 뿌리기 */
    public InsertionSort() {
        for (int i = 0; i < SIZE; i++) {
            arr[i] = (int) (Math.random() * 100) + 1;
        }
    }
    
    /**
     * 배열을 출력할 메서드
     */
    public void print() {
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 1.1번부터 끝 인덱스의 원소를 key값으로 한다!
     * 2.해당 key값보다 큰 값이 나올 때까지 원소를 한칸씩 땡긴다.
     * 3.인덱싱이 끝난 자리에 key값을 집어 넣는다!
     * 최악의 시간복잡도 O(N^2)
     * 최선의 시간복잡도 O(N)
     * 공간복잡도 O(1)
     */
    public void insertionSort() {
        for (int i = 1; i < SIZE; i++) {
            int key = arr[i];
            int j = i - 1;
            for (; j >= 0 && key < arr[j]; j--) {
                arr[j+1] = arr[j];    
            }
            arr[j+1] = key;
        }
    }
    
    public static void main(String[] args) {
        InsertionSort is = new InsertionSort();
//        is.print();
        long time = System.currentTimeMillis();
        is.insertionSort();
        System.out.println(System.currentTimeMillis() - time + "ms");
//        is.print();
    }
    
    
}

참고

위키백과 - 삽입정렬