단순 삽입 정렬

단순 삽입 정렬이란? 선택한 요소를 그보다 더 앞쪽의 알맞는 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘을 뜻한다.

k번째 원소를 1부터 k-1번까지 비교하여 적절한 위치에 끼워넣는 방식이다
버블정렬, 단순 선택 정렬과 함께 대표적인 O(n^2)의 복잡도를 가지는 정렬이고 평균적으로 이 중에서는 빠른 편이다. 하지만 자료구조에 따라 뒤로 밀어내는데 시간이 걸린다(대표적으로 ArrayList가 있겠다).

배열이 작을 경우 상당히 효율적이다. 일반적으로 빠르다고 알려진 알고리즘들 조차 배열의 크기가 작으면 삽입 정렬에 밀린다. 따라서 정렬하는 배열의 크기에 따라 정렬 방식을 크게 고려해야 한다.

단순 선택 정렬과는 다르게 서로 떨어져 있는 요소들을 교환하는 것이 아니라 안정적인 정렬이다. 요소의 비교 횟수와 교환 횟수는 n^2/2회 이다.

단순 삽입 정렬 알아보기

단순 삽입 정렬은 트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷한 방법이다

	int[] arr = {6,4,1,7,3,9,8};

위 배열을 예시로 들어보자 보통 단순 삽입 정렬은 2번째 요소부터 보면 된다.
※k번째 요소를 1부터 k-1까지 훑어 보는 방식이라 첫 요소는 필요가 없다.

이때 2번째 요소인 4를 선택하고, 4를 첫 요소인 6과 비교하고 4는 앞쪽으로 가야 하기에 4를 6앞에 삽입한다. 따라서 6은 자동으로 오른쪽으로 밀린다.

	int[] arr = {4,6,1,7,3,9,8};

이제 3번째 요소 1을 선택해 앞쪽에 삽입하는 과정을 살펴보자. 1을 선택 후, 바로 앞 요소인 6과 비교한다. 6보다 작으니 6은 오른쪽으로 밀고, 그 다음 4와 비교한다. 4보다도 작으니 맨 앞에 두고 4와 6은 오른쪽으로 민다.

	int[] arr = {1,4,6,7,3,9,8};

이제 4번째 요소 7을 꺼내보자. 7을 선택 후 바로앞 요소 6과 비교한다. 6은 7보다 작은 수이기에 6앞의 요소들은 볼것도 없다. 7은 그대로 둔다.

5번째 요소 3을선택한다. 7,6,4와 비교 해 보고 마지막으로 1과 비교한다 3보다 작은 요소를 만났으니 해당 위치에 3을 삽입하고 4,6,7을 오른쪽으로 민다.

위와 같은 방법으로 버블 정렬, 단순 선택 정렬과 마찬가지로 요솟수-1 번 실행하게 되면 마지막 요소는 자동으로 정렬돼 있다.

예제

public class SimpleInsert {
    static void insertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int j;
            int tmp = a[i];
            for (j = i; j > 0 && a[j-1] > tmp; j--) {
                a[j] = a[j-1];
            }
            a[j] = tmp;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("단순 삽입 정렬");
        System.out.print("요솟수: ");
        int[] x = new int[sc.nextInt()];

        for (int i = 0; i < x.length; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = sc.nextInt();
        }

        insertSort(x);

        System.out.println("단순 삽입 정렬 완료");
        for(int i = 0; i < x.length; i++) {
            System.out.println("x[" + i + "]=" + x[i]);
        }
    }
}

추가+

단순 삽입 정렬의 파생형으로 이진 삽입 정렬(binary insertion sort)라는 정렬이 존재한다. 다만 이 알고리즘은 안정적이지 않은 정렬이다.