1.3 정렬_삽입정렬

삽입정렬 : 앞의 배열에서 크기를 비교 후 적절한 위치에 삽입(오름차순)

• 시간복잡도 : O(N^2)
• 버블, 선택정렬은 이미 정렬이 되어 있어도, 반복문을 수행함.
• 버블, 선택정렬과 달리 필요할 때만 정렬의 위치를 바꿈.
• 현재 정렬에서 이전 배열이 정렬되었다고 가정
• 이전 배열의 적절한 위치에 삽입

ex)

int[] arr = {9, 1, 3, 4, 5, 6, 2, 8, 7}; - 오름차순 정렬

1. { _, 9, _ } -> 1 삽입 -> { 1, 9 }
2. { _, 1, _, 9, _ } -> 3 삽입 -> { 1, 3, 9 }
3. { _, 1, _, 3, _, 9, _ } -> 4 삽입 -> { 1, 3, 4, 9 }

               .

               .

               .

               .

             반복

arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}

public class Blog {
 
    public static void main(String[] args) {
        int[] arr = { 9, 1, 3, 4, 5, 6, 2, 7, 8 };
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            int j = i;
            while (j >= 0 && arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                j--;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d", arr[i]);
        }
    }
}
 

삽입정렬의 연산은 최악의 경우 배열의 길이 N에 대히여 N * { ( N + 1 ) / 2 } 번 연산 하므로 시간복잡도는 O(N^2)이다.

• 특정 상황에서 매우 빠름
  •  ex) {2, 3, 4, 5, 6, 7, 8, 9, 1} 처럼 데이터가 거의 정렬된 상황에서는 가장빠른 알고리즘이다.
• 삽입시 배열을 전부 탐색하지 않기 때문에 효율적
• 삽입정렬의 시간 복잡도는 선택정렬, 버블정렬과 같지만, 기대할수 있는 실제 수행 시간은 가장 짧다.
• O(N^2) 알고리즘 중 가장 강력한 알고리즘
• 매 회전 마다 모든 배열 전체를 탐색하지 않기 때문
• 특정 경우에는 배열 탐색을 하지 않고 건너 뜀