Insertion sort

1. Problem

- n개의 정수가 담긴 배열을 오름차순으로 정렬해보자.

- 삽입 정렬은 요소를 적절한 위치에 삽입하는 방법으로 정렬한다.

- i번째의 요소를 정렬할 차례가 됐을 때, [0, i-1]까지는 정렬된 상태라고 가정한다.

- 필요할 때만 요소의 위치를 바꾼다.

 

2. Input

1) int[] arr

 

3. Output

1) 오름차순으로 정렬된 배열을 반환

 

4. Example

// 예시: 2 3 6 1 5 4
// 0번째: 삽일할 위치가 없다. -> (2) 3 6 1 5 4
// 1번째: 3은 2보다 크다. -> (2 3) 6 1 5 4
// 2번째: 6은 3보다 크다. -> (2 3 6) 1 5 4
// 3번째: 1은 2보다 작다. -> (1 2 3 6) 5 4
// 4번째: 5는 3보다 크고 6보다 작다. -> (1 2 3 5 6) 4
// 5번째: 4는 3보다 크고 5보다 작다. -> (1 2 3 4 5 6)

 

5. Code

int[] arr = {6, 3, 5, 9, 1, 10, 7, 2, 4, 8}; // 10개의 요소
int temp = 0;
for(int i=0 ; i<arr.length-1 ; i++) {
    int j = i; // 정렬하고자 하는 요소의 위치. i-1번째 까지는 정렬이 된 상태
    while(j>=0 && arr[j] > arr[j+1]) { // i번째 요소의 적절한 위치를 찾아간다.
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp; j--; // 적절한 위치를 찾을 때까지 인덱스를 감소시킨다. 
    }
}
// 정렬 확인
for(int i : arr)
    System.out.print(i+","); // 1,2,3,4,5,6,7,8,9,10,

- 10개의 요소를 정렬할 때 살펴봐야 하는 총 횟수는 1 + 2 + ... + 9 = 45번의 비교 연산을 해야 한다.

- n개의 요소라면 비교 연산의 총 횟수는 n*(n-1)/2번이다.

- 그러므로 시간 복잡도는 O(n^2)를 따른다.

- 왼쪽이 정렬됐고, 오른쪽에 있는 요소의 위치를 찾아가기 때문에 버를 정렬이나 선택 정렬보다 훨씬 빠르다.

- 거의 정렬된 상태의 배열이라면 삽입 정렬이 압도적으로 빠르다.