[Algorithm] 삽입정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
• 앞쪽에 있는 원소들이 이미 정렬이 되어 있다고 판단하고 어떤 위치에 들어갈 지 판단하게 됩니다.
• 첫 번째 위치는 이미 정렬되어 있다고 판단하고, 두 번째 위치부터 왼쪽으로 이동하면서 자신이 들어갈 위치를 찾습니다.
• 오름차순인 경우는 왼쪽으로 이동하면서 자신보다 큰 값들과 위치를 바꾸고 작거나 같은 값이 나올 경우 탐색을 종료합니다.
• 내림차순인 경우는 왼쪽으로 이동하면서 자신보다 작은 값들과 위치를 바꾸고 크거나 같은 값이 나올 경우 탐색을 종료합니다.
• 선택정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 선택정렬보다 빠르게 동작합니다.
• 최악의 경우 모든 경우의 수를 파악해야 하기 때문에 O(N^2)이 걸리지만, 최적의 경우엔 O(N)의 시간 복잡도를 가지게 됩니다.
• 최악의 경우 : { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }
• 최적의 경우 : { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if(array[j] < array[j-1]) {
                int temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            } else {
                break;
            }
        }
    }

    for (int i : array) {
        System.out.print(i + " ");
    }
}

 

---

참고자료

• 나동빈 - 이코테