Insertion Sort

Insertion Sort (삽입 정렬)?

• 삽입 정렬은 index 1 (2번째) 데이터부터 시작
• 해당 인덱스가 i라면, 바로 앞 (i-1)번부터 0번까지의 데이터들과 차례로 비교하여, 자신보다 큰 값이라면 swap(shift)
• 자신보다 작은 값이라면, 그 index보다 작은 위치의 데이터들은 sorting이 완료되어 있다는 가정을 하고 sorting 종료

핵심 패턴

한 바퀴를 돌 때, 데이터끼리 비교해야하는 최대 횟수: (데이터의 길이 - 1)
n번째 바퀴일때, 처음 기준점이 되는 index번호: n번 (index 1부터 시작하니까)

구현

package SortingAlgorithm;

import java.util.Arrays;

public class InsertionSorting {
    public static void main(String[] args) {
        int[] datas = {9, 1, 8, 2, 7, 3, 6, 4, 5};

        System.out.println("**** 삽입 정렬하기 이전: " + Arrays.toString(datas));

        //처음 기준점이 되는 index 1 (두번째 값), n번째 바퀴일때 기준점이 되는 index n
        //한 바퀴를 돌 때, 데이터끼리 비교해야하는 최대 횟수: (데이터의 길이 - 1)회이지만
        //              index 1부터 시작하므로 index는 datas.length까지
        for(int i=1; i<datas.length; i++){
            int temp = datas[i];

            int j=i-1;
            while(j>=0 && datas[j]>temp) {
                //바로 오른쪽 칸으로 복사해준다
                datas[j+1] = datas[j];
                j--;            
            }
            //한 바퀴 돌고나면 datas[j] = temp 해줘야 하지만
            //반복문 종료 후 이미 j가 -1된채로 반복문 종료되었기 때문에 j+1로 입력 필요
            datas[j+1] = temp;

            System.out.println(i + "번째 정렬: " + Arrays.toString(datas));
        }

        System.out.println("**** 삽입 정렬 후: " + Arrays.toString(datas));
    }
}

**** 삽입 정렬하기 이전: [9, 1, 8, 2, 7, 3, 6, 4, 5]
1번째 정렬: [1, 9, 8, 2, 7, 3, 6, 4, 5]
2번째 정렬: [1, 8, 9, 2, 7, 3, 6, 4, 5]
3번째 정렬: [1, 2, 8, 9, 7, 3, 6, 4, 5]
4번째 정렬: [1, 2, 7, 8, 9, 3, 6, 4, 5]
5번째 정렬: [1, 2, 3, 7, 8, 9, 6, 4, 5]
6번째 정렬: [1, 2, 3, 6, 7, 8, 9, 4, 5]
7번째 정렬: [1, 2, 3, 4, 6, 7, 8, 9, 5]
8번째 정렬: [1, 2, 3, 4, 5, 6, 7, 8, 9]
**** 삽입 정렬 후: [1, 2, 3, 4, 5, 6, 7, 8, 9]

시간복잡도

• 완전 정렬이 되어 있는 상태라면 최선은 O(n)
• 반복문이 두 개라서 O($n^2$)
• 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
• 버블 정렬과 시간복잡도 같음

출처
패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online
https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif