[정렬] Insertion Sort

삽입 정렬의 개념

삽입 정렬 수행도

삽입 정렬이란?

1. 선택 정렬과 다르게 데이터의 삽입할 위치를 찾는 정렬이다.
2. 현재 Key 앞에 위치하는 데이터들은 이미 정렬된 데이터들이며, 정렬이 완료된 데이터들 사이에 Key의 위치를 찾는 것이 삽입정렬이다.
3. 이미 정렬된 데이터일 경우 모든 데이터가 비교를 단 한번만 수행하기 때문에 최선의 경우 O(N)의 성능을 보여준다.

 

동작 방식

1. 리스트 길이(n)의 -1 만큼 반복한다. (맨 앞의 데이터는 제외한다.)

         1-2. 해당 위치에 선택된 데이터를 삽입한다.

         1-1. 현재 선택된 데이터와 앞에 위치한 정렬된 값들을 비교하며 삽입할 위치를 찾는다.

    void sort(int[] numbers) {
				// 1.
        for(int i=1; i<numbers.length; i++) {
            int temp = numbers[i], j;
						// 1-1.
            for(j = i-1; j>=0 && numbers[j] > temp; j--) {
                numbers[j+1] = numbers[j];
            }
						// 1-2.
            numbers[j+1] = temp;
        }
    }

삽입 정렬의 장단점

장점 

1. stable sort 방법이기 때문에, 두 개의 키값을 가지고 정렬을 시도할 수 있다.
2. 굉장히 단순한 로직을 가지고 있다.
3. 대부분의 데이터가 이미 정렬되어 있는 경우 매우 효율적이다.
4. 배열 안에서 모든 과정이 일어나기 때문에 추가적인 메모리 공간이 없다.  -> 공간 복잡도 O(1) 

 

단점

1. key가 되는 데이터를 올바른 위치에 삽입해야 하기 위해서는 앞의 모든 데이터들이 한칸씩 이동을 해야만 한다.
2. 비교적 많은 데이터들의 이동을 포함할 수 밖에 없다.
3. 평균, 최악의 경우 O(n^2)인 비효율적인 정렬이다.

시간 복잡도

best case

1.리스트 길이(n)의 -1 만큼 반복한다. (첫번째 값을 제외한 n-1개)

        1-1. 1번째 데이터부터 n번째 데이터까지 삽입될 위치를 찾는다.

               1, 2, ....... n-1

        1-2. 해당 위치에 선택된 데이터를 삽입한다. 

               1 + 2 + 3 + ...... + n-1 = n(n-1)/2 → O(N^2)

 

worst case

1. 모두 정렬이 되어있는 경우 모든 데이터가 한번씩 밖에 비교를 하지 않기 때문에 O(N)의 시간복잡도를 가진다.                                  1 + 1 + 1 + ..... + 1 = n → O(N)

Insertion Sort vs Selection Sort

1. Selection Sort 같은 경우에는 하나의 데이터를 정렬하기 위해 나머지 모든 요소를 탐색한다.
2. 반면에 Insertion Sort는 필요한 만큼의 요소를 탐색한다.
3. 정리하자면 삽입 정렬은 데이터의 삽입할 위치를 찾는 것이고, 선택 정렬은 가장 작은 데이터를 찾는 방식이다.

정렬들의 비교

https://ybdeveloper.tistory.com/117

정렬 알고리즘 비교