5. Sorting (1)

5. Sorting (1)

주어진 데이터를 특정 기준에 따라 재배열하는 작업을 정렬이라고 합니다. 주어진 데이터에 따라 기준은 얼마든지 달라질 수 있지만, 대표적으로 사용하는 기준은 오름차순 또는 내림차순입니다. 가장 쉬운 예시로 100개의 정수가 포함된 배열이 주어졌을 때 이 배열을 오름차순으로 정렬하는 경우를 생각해볼 수 있을 것입니다. 이때 첫 번째 원소가 최솟값, 마지막 원소가 최댓값임을 쉽게 알 수 있습니다.

또 다른 예시로 카드 게임을 하는데 54장의 트럼프 카드 중에서 조커 2장을 빼려고 하는 경우를 생각해볼 수 있습니다. 처음 개봉한 트럼프 카드라면 정렬이 되어 있어 조커가 맨 앞(혹은 맨 뒤)에 있어 쉽게 조커를 뺄 수 있지만, 카드가 뒤죽박죽 섞여 있다면 조커 2장을 찾기 위해 54장의 카드를 전부 훑어봐야 합니다.

이와 같이 정렬이 완료된 데이터는 특정 기준을 만족하게 됩니다. 이 기준으로부터 부가적인 정보를 손쉽게 얻을 수 있게 되기 때문에, 효율적인 정렬을 위한 알고리즘은 매우 활발히 연구되어 왔습니다.

총 3편의 글에 걸쳐서 정렬 알고리즘에 대해 소개하려고 합니다. 우선 1~2편에서는 비교 기반 정렬 알고리즘을 소개할 예정입니다. 그리고 3편에서는 정수를 효율적으로 정렬하는 방법에 대해 소개할 예정입니다.

이번 글에서는 비교 기반 정렬 알고리즘 중 다소 비효율적인 $\mathcal{O}(n^2)$ 알고리즘을 3개 소개합니다.

---

편의상 정수 $n$개가 담긴 배열을 오름차순으로 정렬하는 상황을 가정하겠습니다.

Selection Sort

선택 정렬(Selection Sort) 알고리즘은 정렬하고자 하는 원소를 선택하여 정렬하는 알고리즘입니다.

우선 배열의 앞부분을 정렬된 영역 A로 잡고, 뒷부분을 그렇지 않은 영역 B로 나눕니다. 그리고 배열을 순회할 때마다 B의 원소 중 최솟값을 찾아 B의 첫 번째 원소와 자리를 바꿉니다. 그러면 정렬된 영역 A가 한 칸 늘어나게 되고 B는 한 칸 줄어들게 됩니다. 이제 이 과정을 반복하면 배열 전체가 정렬됩니다.

그림으로 보면 다음과 같습니다.

처음에는 정렬되지 않은 영역 B가 배열 전체가 됩니다. 배열 전체에서 최솟값을 찾아 B의 첫 번째 원소와 자리를 바꿉니다. 0은 이제 정렬이 되었고, 정렬된 영역 A는 노란색으로 색칠되어 있습니다.

이제 최솟값을 찾아 B의 첫 번째 원소와 자리를 바꾸는 과정을 반복합니다. 정렬된 영역 A가 한 칸씩 늘어납니다.

구현은 다음과 같이 할 수 있습니다.

시간 복잡도를 계산해 보겠습니다. 한 번 순회할 때마다 정렬된 원소의 수가 $1$씩 증가하기 때문에 배열을 총 $n$회 순회해야 합니다. $k$번째 순회를 시작하기 전, 정렬되지 않은 원소는 $n - k + 1$개 이기 때문에 최솟값을 찾기 위해 원소들을 $n - k$번 비교해야 합니다. 따라서 시간 복잡도는

$$\sum_{k = 1}^n (n - k) = n^2 - \frac{n(n + 1)}{2} = \frac{n(n-1)}{2}$$

가 되어 이 알고리즘은 $\mathcal{O}(n^2)$에 동작합니다.

Insertion Sort

삽입 정렬(Insertion Sort) 알고리즘은 배열이 정렬된 상태가 되도록 각 원소를 제 위치에 삽입하는 알고리즘입니다.

선택 정렬과 마찬가지로, 배열의 앞부분을 정렬된 영역 A로, 뒷부분을 그렇지 않은 영역 B로 나눕니다. 이제 B의 첫 번째 원소 $x$에 대하여 A가 정렬된 상태를 유지할 수 있도록 하는 $x$의 위치를 찾아 A에 삽입합니다. 그러면 정렬된 영역 A가 한 칸 늘어나게 되고 B는 한 칸 줄어들게 됩니다. 이 과정을 반복하면 배열 전체가 정렬됩니다.

그림으로 보면 다음과 같습니다.

3, 13, 87을 정렬하는 부분은 생략했습니다. 이제 0을 적절한 위치에 삽입할 차례입니다. 정렬된 영역의 마지막 원소부터 비교합니다. 87, 13, 3을 비교해보니 0이 더 작으므로 0은 맨 앞에 들어가야 합니다. 3, 13, 87을 한 칸씩 밀고, 0을 맨 앞으로 옮깁니다. 정렬된 원소가 1개 늘어 4개가 되었습니다.

96을 정렬하는 과정은 생략했습니다. 54를 적절한 위치에 삽입하기 위해 96, 87과 비교했더니 54가 더 작고, 다음으로 비교한 13에 비해서는 54가 큽니다. 87, 96을 한 칸씩 밀고, 54를 그 자리로 옮깁니다. 정렬된 원소가 1개 늘어 6개가 되었습니다. 이제 같은 과정을 반복합니다.

구현은 다음과 같이 할 수 있습니다.

시간 복잡도를 계산해 보겠습니다. 원소의 개수가 $n$개 이므로 총 $n$회의 삽입이 일어나야 합니다. 그리고 삽입하려는 원소의 위치를 찾기 위해서는 정렬된 원소들과 비교해야 합니다. $k$번째 삽입이 일어나기 전, 정렬된 원소는 $k - 1$개 이고, 최악의 경우 이 원소들과 모두 비교하게 될 수 있으므로 매 삽입마다 $k - 1$회 비교해야 합니다. 따라서 시간 복잡도는

$$\sum_{k = 1}^n (k - 1) = \frac{n(n + 1)}{2} - n = \frac{n(n - 1)}{2}$$

가 되어 이 알고리즘은 $\mathcal{O}(n^2)$에 동작합니다.

시간 복잡도를 계산하는 것이므로 최악의 경우를 상정했지만, 말 그대로 최악의 경우이기 때문에 실제로는 이보다 덜 걸릴 수도 있습니다. 참고로 최악의 경우가 되는 배열은 역순으로 정렬된 배열([10, 9, 8, ..., 1])입니다.

또한, 자료구조에 따라 삽입을 위해 원소들을 한 칸씩 뒤로 밀어줘야 할 수도 있습니다. (배열의 삽입과 유사합니다) 원소의 복사가 굉장히 비효율적인 경우 삽입 정렬의 수행 시간은 매우 길어질 수 있음에 유의해야 합니다.

Bubble Sort

버블 정렬(Bubble Sort) 알고리즘은 양 옆의 원소를 비교하여 더 큰 원소를 배열의 뒤쪽으로 보내는 알고리즘입니다.

이번에는 배열의 앞부분을 정렬되지 않은 영역 B로, 뒷부분을 정렬된 영역 A로 나눕니다. 이제 B의 앞에서부터 양 옆의 원소를 쌍마다 차례로 비교하면서 만약 왼쪽 원소가 오른쪽보다 크다면 두 원소들의 자리를 바꿉니다. 이렇게 하면 B의 마지막까지 왔을 때 B의 마지막에는 가장 큰 원소가 위치하고 있을 것입니다. 그러면 정렬된 영역 A가 한 칸 늘어나게 되고, B는 한 칸 줄어들게 됩니다. 이제 다시 B의 앞부터 쌍마다 비교하는 과정을 반복하면 배열 전체가 정렬됩니다.

그림으로 보면 다음과 같습니다.

처음에는 배열이 전부 정렬되지 않았기 때문에, 배열 전체가 영역 B입니다. B의 앞에서부터 양 옆의 원소를 쌍마다 비교합니다. (3, 13), (13, 87)을 비교하니 모두 오른쪽 원소가 크기 때문에 자리를 바꾸지 않고 넘어갑니다.

이제 (87, 0)을 비교하니 왼쪽 원소가 크므로 자리를 바꿉니다. (87, 96)은 자리를 바꾸지 않습니다. (96, 54)는 비교하니 왼쪽 원소가 크므로 자리를 바꿉니다.

위 과정이 반복되어 최종적으로 영역 B의 맨 끝에는 가장 큰 원소가 위치하게 됩니다. 정렬된 영역 A가 한 칸 늘었습니다. 이제 다시 영역 B의 맨 앞으로 돌아가 마찬가지로 쌍마다 비교합니다. 비교가 끝나면 현재 B에서 가장 큰 원소인 87이 B의 맨 끝에 위치하게 되고, 마찬가지로 영역 A가 한 칸 늘어나게 됩니다.

구현은 다음과 같이 할 수 있습니다.

시간 복잡도를 계산해 보겠습니다. B의 원소들을 쌍마다 비교하는 과정을 마칠 때마다 정렬된 원소가 하나씩 증가하기 때문에 이 과정은 총 $n$번 일어납니다. $k$번째 과정을 시작하기 전, 영역 B의 원소는 $n - k + 1$개 이므로 쌍마다 차례로 비교하면 $n - k$회 비교가 일어납니다. 따라서 시간 복잡도는

$$\sum_{k = 1}^n (n - k) = n^2 - \frac{n(n + 1)}{2} = \frac{n(n-1)}{2}$$

가 되어 이 알고리즘은 $\mathcal{O}(n^2)$에 동작합니다.

---

이번 글에서는 $\mathcal{O}(n^2)$에 동작하는 정렬 알고리즘을 소개했습니다. 여러분은 카드를 정렬할 때 어떤 알고리즘을 쓰시는 것 같나요? 위에서 소개한 알고리즘 중에 있나요? 아니면 더 효율적으로 정렬하시나요? 다음 글에서는 이보다 효율적으로 동작하는 정렬 알고리즘을 소개하겠습니다.