정렬 #3) 삽입 정렬

삽입 정렬은 말그대로 이미 정렬되어 있는 배열에 새로운 원소를 삽입하는 것이다.

아래는 오름차순 정렬에 대한 예시이다.

 

---

---

 

삽입하고자 하는 값을 key라고 하자.

key를 배열의 2번째 원소부터 시작하여 3번째, 4번째... 로 설정하게 되면, key보다 왼쪽에 있는 원소들은 이미 정렬이 되어 있는 상태가 된다.

따라서 우리는 key가 삽입될 위치를 찾기만 하면 된다.

 

찾는 방법은 간단하다. 왼쪽으로 계속 이동하다가 key 값보다 작거나 같은 값이 나올 때 멈추면 된다.

물론 이동이라고 해서 swap으로 구현하면 안 된다.

key 값은 따로 저장해두고, 배열을 한 칸씩 shift시키다가 자리를 찾으면 그 때 swap하는 편이 낫다.

 

시간 복잡도는 버블 정렬, 선택 정렬과 동일한 O(n^2)이지만 최선의 경우에는 O(n)이 될 수도 있다.

최악의 경우로서, 내림차순으로 정렬된 배열을 오름차순으로 다시 정렬하려 한다면 1 + 2 + 3 + ... + (n - 1) 번의 비교가 필요하므로 O(n^2)의 시간 복잡도를 가지지만,

이미 오름차순으로 정렬이 되어 있는 경우에는 아무런 shift가 일어나지 않고 그냥 배열을 순회하는 형태가 되어버린다. 따라서 O(n)이다.

 

---

int[] num = { 6, 4, 5, 7, 1 };
int key, j;

for (int i = 1; i < num.Length; i++)
{
    key = num[i];
    j = i - 1;

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

    num[j + 1] = key;
}

 

정렬 결과