삽입 정렬

설명

1. 정렬되지 않은 배열의 원소를 하나씩 key 값으로 선택한다.
2. key 값을 기준으로 좌측은 항상 정렬된 상태이다.
3. key 값을 정렬된 좌측 원소들과 비교하며, key 값이 좌측 원소보다 작다면 정렬된 원소들을 오른쪽으로 한 자리씩 이동시켜 key 값이 들어갈 자리를 만든다.
4. key 값이 좌측의 정렬된 원소보다 크거나 같을 때 비교를 중지하고 해당 위치에 key 값을 삽입한다.
5. 모든 원소가 정렬될 때까지 1~4번까지 반복한다.

• i는 우측 방향으로 이동하며 key 값을 새롭게 설정해 나간다.
• j는 이미 정렬된 좌측 방향으로 이동하며 key 값과 비교하여 key 값보다 원소가 클 경우 우측으로 원소를 밀어서 key 값을 삽입할 공간을 만든다.

구현

public static void insertionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int j = i - 1;
        int key = arr[i];

        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

삽입 정렬 구현 코드

시간복잡도

• 최선의 경우: O(N)
  이미 정렬 되어 있을 경우 추가 좌측 원소에 대한 비교가 이뤄지지 않기 때문
• 최악의 경우: O(N^2)
  모든 원소가 역순으로 정렬되어 있을 경우 매 key 값마다 좌측의 가장 끝까지 공간을 계속 밀어내야 하기 때문에