![Featured Image for [알고리즘] Insertion Sort](https://upload.wikimedia.org/wikipedia/commons/e/ef/Sorting_shaker_sort_anim.gif)
Insertion sort(삽입 정렬)는 말 그대로 정렬된 배열에 새로운 요소를 삽입하여 정렬을 확장해 나가는 알고리즘이다. 배열을 처리할 때, 전체 배열 중 왼쪽 부분은 이미 정렬된 상태이고, 오른쪽 부분은 아직 정렬되지 않은 상태로 남아 있다. 삽입 정렬은 이 정렬되지 않은 부분에서 하나씩 요소를 가져와서, 정렬된 배열의 어느 위치에 삽입해야 할지 결정하는 방식으로 동작한다.
이 알고리즘에서 두 개의 주요 루프가 존재한다.
void insertionSort(int *arr, int N) {
for (int i = 1; i < N; i++) { // 루프_1
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) { // 루프_2
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
for (int i = 1; i < N; i++)
이 부분은 정렬되지 않은 배열의 인덱스를 하나씩 선택하는 루프이다. 정렬되지 않은 부분에서 하나씩 가져와서 처리할 것이기 때문에, 이 루프는 결국 인덱스 1 부터 N - 1 까지 모든 인덱스를 순차적으로 처리하게 된다. 선택한 인덱스 int key 에 저장한다. 여기서 선택된 int key를 가지고 다음으로 넘어가 while 루프에서 지금 선택한 인덱스가 정렬된 부분에서 어느 위치에 들어가야 정렬 상태가 유지될지 결정한다.
이때, 왜 인덱스를 1부터 시작하는지 궁금할 수 있다. 사실, 0번 인덱스부터 시작해도 문제는 없다. 하지만 처음 상황에서, 아직 정렬을 시작하지 않은 상태에서는 굳이 0번 인덱스부터 처리할 필요가 없다. 0번 인덱스는 이미 하나의 요소로만 이루어졌기 때문에, 크기가 1인 배열은 정렬된 상태라고 가정할 수 있다. 따라서, 굳이 0번부터 시작하지 않고, 1번 인덱스부터 정렬을 시작하면 된다.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
이 부분은 선택된 요소가 정렬된 배열의 어느 위치에 삽입될지 결정하는 루프이다. 여기서 정렬된 부분을 탐색하는 인덱스는 j로, i - 1에서 시작한다. 즉, j는 현재 정렬해야 할 요소(i)의 바로 왼쪽에 있는 값부터 비교를 시작하는데, 이 말은 j가 i - 1에서 0까지 거꾸로 탐색하며, 정렬된 배열에서 적절한 위치를 찾아가게 된다는 의미이다. 코드를 더 자세히 분석해보자.
j >= 0:
j가 0보다 작아지면 배열의 범위를 벗어나게 되므로, 배열을 넘어가는 것을 방지하기 위해 이 조건이 필요하다.
arr[j] > key:
이 조건은 현재 비교 중인 요소 arr[j]가 key보다 큰지 확인한다. 만약 크다면, key가 arr[j]보다 왼쪽에 위치해야 하므로, arr[j]를 오른쪽으로 이동시킨다. 이 과정이 반복되면서 key의 올바른 위치가 결정된다.
arr[j + 1] = arr[j];:
이 줄은 arr[j]를 오른쪽으로 한 칸 이동시키는 역할을 한다. 즉, arr[j] 값을 arr[j + 1]에 복사하여, arr[j]가 있던 자리는 비워지게 된다. 이 자리가 나중에 key가 들어갈 자리가 될 수 있다.
j--;:
j 값을 1 줄여 왼쪽으로 이동하면서 계속해서 key보다 큰 값들을 오른쪽으로 밀어낸다. 이 과정을 반복해 key가 들어갈 적절한 위치를 찾는다.
arr[j + 1] = key;:
while 루프가 끝난 후에는 key가 들어갈 자리가 정해진다. 이때 arr[j + 1] 위치가 key가 삽입될 정확한 위치이다. while 루프가 종료되는 시점에서는 arr[j]가 key보다 작거나 같거나, j가 배열을 벗어난 상태이므로, key는 그 다음 위치인 j + 1에 삽입된다.
Insertion sort은 결국 리스트를 순차적으로 하나씩 살펴보며, 현재 요소를 이미 정렬된 부분에 알맞은 위치에 삽입하여 전체 리스트를 정렬하는 알고리즘이다. 예를 들어, 카드 게임에서 손에 카드를 한 장씩 추가하면서 이미 정렬된 손에 새로운 카드를 올바른 위치에 끼워 넣는 과정과 같다. 이제 귀납법을 통해 Insertion sort 알고리즘이 항상 입력된 리스트를 올바르게 정렬하는지 그 정확성 을 증명해보자.
명제 P(i): 반복문이 i번째 반복 후에 리스트의 앞부분 A[0…i−1]은 정렬되어 있다.
증명을 위해 위와 같은 명제를 설정하자. 즉, 알고리즘이 i번째 요소까지 처리했을 때, 처음부터 i번째 요소까지의 부분 리스트가 정렬되어있음을 나타낸다.
귀납법은 다음 네 가지 단계로 이루어진다.
반복문이 시작하기 전에 리스트의 앞부분 A[0...-1]은 정렬되어 있다. A[0...-1]은 요소가 없는 빈 리스트이므로, 빈 리스트는 이미 정렬된 상태이다. 따라서 P(0)은 참이다.
임의의 자연수 k에 대해 P(k)가 참이다. 즉, 리스트의 앞부분 A[0...k-1]은 정렬되어 있다.
P(k)가 참일 때, P(k+1)도 참이라는 것은 곧 A[0...k]이 정렬되어 있음을 보여야 하는 것! 알고리즘은 k번째 요소 A[k]를 고려해보자. 이미 정렬된 리스트 A[0...k-1]에서 A[k]의 적절한 위치를 찾는다. A[k]를 해당 위치에 삽입한다. 즉, 정렬된 리스트에 새로운 요소를 올바른 위치에 삽입하면, 리스트는 여전히 정렬된 상태를 유지한다. 따라서 A[0...k]은 정렬되어 있으며, P(k+1)은 참이다.
인덱스 i가 리스트의 길이 n보다 작을 때까지 반복한다. 각 반복마다 i는 1씩 증가한다. i가 n에 도달하면 반복문이 종료된다. 알고리즘은 유한한 단계 내에 반드시 종료한다.
A[0...n-1]은 정렬되어 있다.선택정렬에서 Best Case는 결국 이미 정렬이 된 배열이 Input으로 들어왔을 경우이다. 해당 경우의 시간복잡도를 자세하게 살펴보자.
void insertionSort(int *arr, int N) {
for (int i = 1; i < N; i++) { // 1. (N - 1) Times
int key = arr[i]; // 2. (N - 1) Times
int j = i - 1; // 3. (N - 1) Times
while (j >= 0 && arr[j] > key) { // 4. 0 Times
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 5. (N - 1) Times
}
}
for (int i = 1; i < N; i++)
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
j의 초기값이 -1 이므로 한번도 실행되지 않는다.arr[j + 1] = key;
따라서 선택정렬의 Best Case의 경우, 위 코드의 시간복잡도는 아래와 같다.
$$ \Omega(4n - 4) ≈ O(N) $$
선택정렬에서 Worst Case는 역순으로 정렬된 배열이 Input으로 들어왔을 경우이다. 해당 경우의 시간복잡도를 자세하게 살펴보자.
void insertionSort(int *arr, int N) {
for (int i = 1; i < N; i++) { // 1. (N - 1) Times
int key = arr[i]; // 2. (N - 1) Times
int j = i - 1; // 3. (N - 1) Times
while (j >= 0 && arr[j] > key) { // 4. 1/2 * (N - 1)N Times
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 5. (N - 1) Times
}
}
for (int i = 1; i < N; i++)
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
i가 1 일때 j는 0 이고, 총 1 번 실행된다.i가 2 일때 j는 1 이고, 총 2 번 실행된다.i가 (N - 1) 일때 j는 (N - 2)이고, 총 (N - 1) 번 실행된다.1 + 2 + ... + (N - 1) 의 합 만큼 실행된다.arr[j + 1] = key;
따라서 선택정렬의 Best Case의 경우, 위 코드의 시간복잡도는 아래와 같다.
$$ O(\frac{1}{2}N^2 + \frac{7}{2}N - 4) ≈ O(N^2) $$