삽입 정렬

개요

손 안의 카드 뭉치를 정리하는 것과 같은 원리.
특정 카드가 해당 카드의 앞 카드 뭉치 중 적절한 위치에 삽입하는 방법의 정렬.

---

복잡도

	최악	평균	최소
Big O 표기법	O(n^2)	O(n^2)	O(n)

---

알고리즘 절차

1. 첫번째 요소는 스킵하고 2 번째 요소부터 검사를 시작함.
2. i 번째 요소를 임시로 tmp 변수에 담아놓는다.
3. i 번째 요소를 i-X 번째 요소와 비교한다. 
   만약 i 번째 요소가 더 작다면 i-X 번째 요소에 i-X+1 번째 위치에 놓아 빈 공간을 마련해줌. 이 경우, X값을 +1해서 다시 수행한다.
   만약 i 번째 요소가 더 크다면 i-X+1위치에 tmp에 저장한 값을 위치시킴. 이 경우, 3번의 루프를 탈출한다.

---

자바 코드

class Insert {
    public static void main(String[] args) {
        int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543};

        insertSort(testCase1);

        for (int item : testCase1) {
            System.out.println(item);
        }
    }
    
    public static void insertSort(int[] arr) {
        for(int i=1; i<arr.length; i++) {
            int tmp = arr[i];
            
            int j;
            for(j=i-1; j>=0 && arr[j] > tmp; j--) {
                arr[j+1] = arr[j];
            }   arr[j+1] = tmp;
        }
    }
}