[Algorithm] Insertion Sort (삽입 정렬)

1. Insertion Sort (삽입 정렬)

 

삽입 정렬은 N개의 원소 배열을 정렬 시에 배열을 정렬이 되어있는 부분과 정렬이 되지 않는 부분 두 부분으로 나누어 비교를 하여 정렬하는 알고리즘이다. 매 정렬 시에 정렬을 하지 않은 부분의 한 원소를 선택해서 정렬이 된 부분과 비교하여 원소의 위치를 찾아서 해당 위치에 삽입하는 방식으로 정렬한다.

 

삽입 정렬을 통해서 오름차순으로 정렬 시에 다음과 같은 순서를 거친다.

• 배열의 정렬을 1부터 N까지 반복한다.
• i-1까지의 값이 정렬되어 있을 때 정렬을 하는 대상이 되는 값이 i번째 값이 된다. 이때 먼저 i-1 번째 값과 비교하여 i-1 번째 값이 더 큰 경우 자리를 바꾼다.
• 이 과정을 i-1부터 0번까지 비교를 진행하게 되는데, 이때 한칸 앞의 값이 더 작은 경우에 반복을 중단하고 i+1 값을 정렬 대상으로 선택해서 정렬을 반복한다.

 

2. Insertion Sort 구현

 

삽입 정렬은 1부터 N까지 반복을 진행하는데 매 i번째 반복에서 i-1부터 0까지의 값들과 비교를 하여 정렬을 진행한다. 앞부분이 정렬된 배열, 뒷부분이 정렬되지 않은 부분이 되어서 비교를 진행한다.

 

- Java로 구현한 Insertion Sort

import java.util.Arrays;

import Algorithm.Sorting.Sort;

public class InsertionSort implements Sort {
    private int[] array;

    public InsertionSort(int[] array) {
        this.array = Arrays.copyOf(array, array.length);
    }

    @Override
    public int[] sort() {
        int N = array.length;
        for(int i = 1; i < N; i++) {
            for(int j = i - 1; -1 < j; j--) {
                if(array[j] < array[j + 1])
                    break;
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        return array;
    }
    
}

 

 

3. Insertion Sort 복잡도

- 시간 복잡도: O(N^2)

- 공간 복잡도: O(1)

 

 

[reference]

- https://www.geeksforgeeks.org/insertion-sort/

Insertion Sort - GeeksforGeeks

- https://ko.wikipedia.org/wiki/삽입_정렬

삽입 정렬 - 위키백과, 우리 모두의 백과사전