[Algorithm] 삽입정렬(Insertion Sort)

삽입정렬이란?

현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법.

선택정렬, 버블정렬과는 다르게 안정 정렬.

 

삽입정렬의 과정(오름차순 기준)

1. 인덱스 1부터 시작한다. 현재 인덱스를 타겟 인덱스로 하고 변수에 넣는다. 이 변수보다 이전 인덱스가 작으면 이전 인덱스의 값을 그 다음 인덱스에 넣어준다. 

2. 만약에 인덱스 2가 타겟이고, 타겟의 값이 인덱스 1보다 작다면 그 다음 인덱스에 넣는다. 또 인덱스 0이 타겟보다 작으면 또 그 다음 인덱스에 넣는다. 그리고 타겟 인덱스의 값을 인덱스 0에 넣어준다.

3. 이를 계속 반복한다. 

 

구현 코드

import java.util.Scanner;

public class Main {

    private int[] solution(int n, int[] list) {
        int i, j;
        for (i = 1; i < n; i++) {
            int key = list[i];
            for (j = i - 1; j >= 0; j--) {
                if (key < list[j])  list[j + 1] = list[j];
                else    break;
            }
            list[j + 1] = key;
        }

        return list;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main T = new Main();
        int n = scanner.nextInt();
        int[] list = new int[n];
        for (int i = 0; i < n; i++) list[i] = scanner.nextInt();
        for (int i : T.solution(n, list)) System.out.print(i + " ");
    }
}

 

삽입정렬 알고리즘의 장점

• 안정한 정렬 방법
• 레코드 수가 적을 경우 알고리즘이 간단하므로 다른 복잡한 정렬 알고리즘보다 유리할 수 있다.
• 이미 정렬되어있는 레코드일 경우 효율적일 수 있다.

삽입정렬 알고리즘의 단점

• 많은 레코드들의 이동을 포함한다. 
• 레코드 수가 많고 크기가 클 경우에 적합하지 않다.

 

시간 복잡도

이미 모든 레코드가 정렬되어 있는 경우

비교 횟수: 이동이 없이 1번의 비교만 이루어진다.

외부 루프: (n-1)번 -> O(n)

 

레코드가 역순으로 정렬되어 있는 경우

비교 횟수: 외부 루프 안의 각 반복마다 i번의 비교를 수행

외부 루프: (n-1)+(n-2)+...+2+1 = n(n-1)/2 = O(n^2)

 

 

References

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog