Insertion Sort (삽입정렬)

삽입정렬(Insertion Sort)란?

삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

선택정렬이나 버블정렬과 같은  O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않기 때문에 시간 복잡도가 O(n)이 된다.

예를 들어 카드 게임을 할 때, 내 손에는 이미 정렬된 카드가 있고, 새로운 카드를 받아 카드 사이의 올바른 자리를

찾아 삽입함으로써 정렬이 유지되게 하는 것이다.

import java.util.Scanner;

/**
 * Created by Itner on 2017. 7. 19..
 */
public class InsertionSort_Rz {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.print("Input Array Size : "); // 배열 사이즈 입력
        int size = scan.nextInt();

        System.out.print("Input Array Value : "); // 배열 값 입력
        int[] list = new int[size];

        for (int i = 0; i < size; i++) {
            list[i] = scan.nextInt();
        }

        for (int i = 0; i < (list.length - 1); i++) {
            int KEY = list[i + 1];
            int j = i;

            while(j >= 0){ // KEY부터 하나씩 내려가며 값을 비교한다.
                if(list[j] <= KEY){ break; }

                list[j + 1] = list[j];
                j--;
            }
            list[j + 1] = KEY;
        }

        /* 처음 코드를 작성할 때 아래와 같이 구현하였는데,
        /* 삽입정렬은 정렬된 배열에 대해서는 한번만 비교해서 시간 복잡도가 O(n)이 되어야하는데
        /* 아래 코드는 무조건 O(n2)이 되었다.
        for (int i = 0; i < (list.length - 1); i++) {
            int KEY = i + 1;

            for (int j = i; j > -1; j--) {
                if(list[j] > KEY){
                    temp = list[j];
                    list[j] = KEY;
                    KEY = list[j];
                }
            }
        }
        */
    }
}

※ 참조 :

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

https://m.blog.naver.com/PostView.nhn?blogId=madplay&logNo=220229003111&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F