[[분류:정보]]
==개요==
이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다.
어떤 항목들을 정렬하는 알고리즘으로, 매우 다양한 방법과 시간복잡도를 가진다. 배열뿐만 아니라 힙과 같은 트리 구조 등을 사용할 수 있다. 분석에 관해서는 [[시간 복잡도]] 문서 참고.
==기초적인 정렬 알고리즘==
===선택 정렬(Selection Sort)===
가장 작은(또는 큰) 원소를 찾아 맨 앞(또는 뒤)의 원소와 교환하는 과정을 반복하여 전체를 정렬하는 방식이다. 본 문서에서는 가장 큰 원소를 찾는 것을 기준으로 서술한다.
====정렬 의사 코드====
다음은 선택 정렬의 의미를 간이화하여 서술한 코드이다.
{{{#!syntax java
selectionSort(A[], n):
for last ← n-1 downto 1
A[0…last] 중 가장 큰 수 A[k]를 찾는다.
A[k] ↔ A[last]
}}}
다음은 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다.
{{{#!syntax java
selectionSort(A[], n):
for last ← n-1 downto 1
k ← theLargest(A, last)
tmp ← A[k]; A[k] ← A[last]; A[last] ← tmp
theLargest(A[], last):
largest ← 0
for i ← 1 to last
if (A[i] > A[largest])
largest ← i
return largest
}}}
====분석====
의사코드 1을 보자. 선택 정렬의 수행 시간은 모든 경우에 [math(\Theta(n^2))]이다. for 루프는 [math(n-1)]번 순환하고, index 교환은 상수 시간이 든다. 큰 수를 찾는 것은 작업은 부분 배열의 크기에 비례한다.[* 크기가 k인 배열에서 가장 큰 수를 찾는 데는 [math(k-1)]번의 비교가 필요하다.] 부분 배열의 크기는 for문에서 n부터 시작하여 2까지 감소한다. 그러므로 비교하는 총 횟수는 [math((n-1)+(n-2)+…+1=\dfrac{n(n-1)}{2})], 즉 [math(\Theta(n^2))]이다.
===버블 정렬(Bubble Sort)===
인접한 두 요소를 반복적으로 비교하고, 순서가 맞지 않으면 서로 자리를 바꾸는 방식으로 데이터를 정렬하는 알고리즘이다.
====정렬 의사 코드 ====
다음은 버블 정렬의 의미를 간이화하여 서술한 코드이다.
{{{#!syntax java
bubbleSort(A[], n):
for last ← n-1 downto 1
for i ← 0 to last-1
if (A[i] > A[i+1])
A[i] ↔ A[i+1]
}}}
다음은 이미 정렬이 완료된 상태이면 작업을 종료하여 효율을 높인 코드이다.
{{{#!syntax java
bubbleSort(A[], n):
sorted ← FALSE
for last ← n-1 downto 1
sorted ← TRUE
for i ← 0 to last-1
if (A[i] > A[i+1])
A[i] ↔ A[i+1]
sorted ← FALSE
if (sorted) return
}}}
====분석====
===삽입 정렬(Insertion Sort)===
이미 정렬된 부분 데이터에 새로운 데이터를 하나씩 비교하며 올바른 위치에 '삽입'하여 정렬을 완성하는 알고리즘이다.
====정렬 의사 코드====
다음은 삽입 정렬의 의미를 간이화하여 서술한 코드이다.
{{{#!syntax java
insertionSort(A[], n):
for i ← 1 to n-1
A[0…i]의 적합한 자리에 A[i]를 삽입한다.
}}}
다음은 재귀를 이용한 코드이다.
{{{#!syntax java
insertionSort(A[], n):
if (n>1)
insertionSort(A[], n-1)
A[0…n-1]의 적합한 자리에 A[n-1]를 삽입한다.
}}}
다음은 적합한 자리를 찾는 로직을 풀어 서술한 코드이다.
{{{#!syntax java
insertionSort(A[], n):
for i ← 1 to n-1
newItem ← A[i]
for (j←i-1; 0 ≤ j and newItem < A[j]; j--)
A[j] ← A[j+1]
A[j+1] ← newItem
}}}
====분석====
==고급 정렬 알고리즘==
전체 리스트를 절반으로 계속 나누어 각 부분을 정렬한 후, 다시 병합하는 분할 정복 기반의 정렬 알고리즘이다. 합병 정렬이라고도 한다.
===병합 정렬(Merge Sort)===
====정렬 의사 코드====
다음은 병합 정렬의 의미를 간단히 서술한 코드이다.
{{{#!syntax java
mergeSort(A[], p, r):
if (p < r)
q ← ⌊(p+r)/2⌋
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
merge(A[], p, q, r):
정렬된 두 배열 A[p…q]와 A[q+1…r]을 합쳐
정렬된 하나의 배열 A[p…r]을 만든다.
}}}
다음은 병합 함수(merge)를 풀어 서술한 코드이다.
{{{#!syntax java
merge(A[], p, q, r):
i ← p; j ← q+1; t ← 0
while (i ≤ j q and j ≤ r)
if (A[i] ≤ A[j]) tmp[t++] ← A[i++]
else tmp[t++] ← A[j++]
while (i ≤ q)
tmp[t++] ← A[i++]
while (j ≤ r)
tmp[t++] ← A[j++]
i ← p; t ← 0
while (i ≤ r)
A[i++] ← tmp[t++]
}}}
====분석====
병합 정렬의 수행 시간은 모든 경우에 [math(\Theta(n\log n))]이다. 이 알고리즘은 비교 횟수를 기준으로 수행 시간을 분석해도 되지만 비교 횟수보다 더 잦은 작업이 있다. 바로 원소를 옮기는 작업으로, A[]와 tmp[]를 번갈아 옮기기 때문에 어떤 경우든 [math(2n)]번의 이동이 일어난다. 비교횟수를 기준으로 분석하면 이 때는 [math(2n)] 대신 [math(n/2)] ~ [math(n-1)]이 된다. 점근적 분석 결과는 원소 이동 횟수와 비교 횟수가 동일하지만 시간을 지배하는 작업을 하나 정한다면 이동 횟수가 더 정확한 기준이 된다. 크기가 m인 배열을 병합 정렬로 처리하는 시간을 T(n)이라고 하면 다음과 같다.
[math({\rm{T}}(n)=\begin{cases}\displaystyle 1 & \quad (n = 1) \\\displaystyle 2T(\frac{n}{2})+2n &\quad (n > 1) \end{cases} )]
[[시간 복잡도#s-3.3|마스터 정리]]를 사용하면 [math(\Theta(n\log n))]이라는 것을 알 수 있다.
===퀵 정렬(Quick Sort)===
분할 정복 기법을 사용하여 기준값(피벗)을 중심으로 데이터를 작은 값과 큰 값으로 나누고, 이 과정을 재귀적으로 반복하여 매우 빠르게 데이터를 정렬하는 알고리즘이다.
====정렬 의사 코드====
다음은 퀵 정렬의 의미를 간단히 서술한 코드이다.
{{{#!syntax java
quickSort(A[], p, r):
if (p < r)
q ← partition (A, p, r)
quickSort(A, p, q-1)
quickSort(A, q+1, r)
partition(A[], p, r):
배열 A[p…r]의 원소들을 기준 원소인 A[r]을 기준으로 양쪽으로 재배치하고
기준 원소가 자리한 위치를 리턴한다.
}}}
다음은 분할 함수(partition)을 풀어 서술한 코드이다.
{{{#!syntax java
partition(A[], p, r):
x ← A[r]
i ← p-1
for j ← p to r-1
if (A[j] < x)
A[++i] ↔ A[j]
A[i+1] ↔ A[r]
return i+1
}}}
====분석====
[[시간 복잡도]]의 점근적 형태가 상황에 따라 달라진다. 우선 분할은 배열을 왼쪽부터 끝까지 한 번 훑어나가는 작업이므로 [math(\Theta(n))]의 시간이 든다.
* '''최선의 경우''': 항상 반반씩 균등하게 분할될 때이므로, 점화식이 [math(T(n)=2T(\frac{n}{2})+\Theta(n))]이 된다. 즉 [[시간 복잡도#s-3.3|마스터 정리]]를 사용하면 [math(\Theta(n\log n))]이라는 것을 알 수 있다.
* '''최악의 경우''': 계속해서 한쪽은 하나도 없고 다른 쪽에 다 몰리도록 분할이 되는 경우이다. 이 때는 점화식이 [math(T(n)=T(n-1)+\Theta(n))]이므로 [[시간 복잡도#s-3.1|반복 대치]]를 사용하면 [math(\Theta(n^2))]라는 것을 알 수 있다.
* '''평균적인 경우''': 크기 [math(n)]인 배열의 피벗이 [math(i)]등이면 1구역과 2구역의 크기는 [math(i-1:n-1)]가 된다. 따라서 점화식은 [math(T(n)=T(i-1)+T(n-i)+\Theta(n))]이고, 평균 시간으로 나타내면 [math(T(n)=\frac{1}{n}\sum_{i=1}^ n ({T(i-1)+T(n-i)})+\Theta(n))]. [[시간 복잡도#s-3.2|추정 후 증명]]을 사용하면 [math(\Theta(n\log n))]라는 것을 알 수 있다. 이 증명은 하위 문단으로 따로 서술한다.
=====평균적인 경우의 증명=====
[math(T(2) \leq c2\log 2)]를 만족하도록 충분히 큰 [math(c)]를 잡을 수 있으므로, [math(2<k<n)]인 모든 [math(k)]에 대해 [math(T(k) \leq ck\log k)]가 성립한다고 가정하자.
[math(T(n)=\frac{1}{n}\sum_{i=1}^ n ({T(i-1)+T(n-i)})+\Theta(n))]
[math(=\frac{2}{n}\sum_{k=1}^ {n-1} T(k)+\Theta(n))]
[math(=\frac{2}{n}\sum_{k=2}^ {n-1} T(k)+\Theta(n))][* log를 사용하기 위해 약간의 트릭을 쓴 것이다. log 1 = 0이므로 부등식을 만들 수 없어 k가 0인 경우와 1인 경우를 제외시켰다. 그런데도 부등호 대신 등호를 사용한 것은 이 두 항, 즉 T(0)과 T(1)을 Θ(n)에 집어넣어 버렸기 때문이다. 이러한 기법을 '흡수'라고 한다. 흡수는 상수 번만 해야지 그렇지 않으면 시간복잡도 분석에 오류가 생긴다. 여기에서는 단 한 번 하는 것이 고작이므로 여전히 Θ(n)는 일차함수다.]
[math(\leq\frac{2}{n}\sum_{k=2}^ {n-1} ck \log k+\Theta(n))]
[math(\leq\frac{2c}{n}\sum_{k=2}^ {n-1} (\frac{1}{2}n^2 \log n -\frac{1}{8}n^2)+\Theta(n))]
[math(=cn\log n - \frac{cn}{4}+\Theta(n))]
[math(\leq cn \log n)]
4번째 줄에서 5번째 줄로 넘어가는 과정은 다음과 같다.
[math(\sum_{k=1}^ {n-1} k \log k = \sum_{k=1}^ {⌈n/2⌉-1} k \log k + \sum_{k=⌈n/2⌉}^ {n-1} k \log k)]
[math(\sum_{k=1}^ {n-1} k \log k \leq (\log n-1) \sum_{k=1}^ {⌈n/2⌉-1} k + \log n\sum_{k=⌈n/2⌉}^ {n-1} k )][* 오른쪽 첫 번째 항의 log k는 log (n/2)=log n - 1로 상한을 잡을 수 있고, 두 번째 항의 log k는 log n으로 상한을 잡을 수 있기 때문이다.]
[math(= \log n \sum_{k=1}^ {n-1} k - \sum_{k=1}^ {⌈n/2⌉-1} k )]
[math(\leq \frac{1}{2}n^2 \log n - \frac{1}{8}n^2)]
[math(\sum_{k=2}^ {n-1} k \log k \leq \sum_{k=1}^ {n-1} k \log k)]이므로 [math(\sum_{k=2}^ {n-1} k \log k \leq \frac{1}{2}n^2 \log n - \frac{1}{8}n^2)]이다.
===힙 정렬(Heap Sort)===
힙 자료구조를 이용해 데이터를 정렬하는 알고리즘으로, 배열을 최대 힙(또는 최소 힙)으로 만든 뒤, 루트(가장 크거나 작은 값)를 배열의 마지막 요소와 교환하고 힙 크기를 줄이는 과정을 반복하는 알고리즘이다. 본 문서에서는 가장 큰 원소 맨 위의 노드에 삽입하는 것을 기준으로 서술한다.
우선 힙이 무엇인지 정확히 알아보자. 1) 완전 이진 트리 구조를 사용하며 2) 모든 노드는 값을 갖고, 그것은 자식 노드(들) 값보다 크거나 같다.
완전 이진 트리 구조의 경우 논리적으로는 트리지만, 구현은 배열로 한다. 맨 위의 노드에서 차례로 내려가며 왼쪽에서 오른쪽으로 A[0], A[1], … A[n]이라고 할 수 있다. A[k]의 자식은 A[2k+1], A[2k+2]이며 부모는 A[⌊(k-1)/2⌋]이다. 이를 이용하여 완전 이진 트리를 힙으로 바꿀 수 있는데, 이를 '스며내리기'라고 한다. 스며내리기는 자식이 존재하는 가장 밑의 노드부터 차근차근 올라오며, 노드가 자식보다 작으면 자식과 교환한다.
힙 정렬은 힙에서 루트에 위치한 최대 원소를 제거한 뒤, 스며내리기 연산을 통해 힙 특성을 복구하고, 이렇게 얻은 최대 원소를 배열의 뒤쪽부터 차례로 저장해 나가는 방식의 정렬이다.
====힙 만들기 의사코드====
다음은 스며내리기를 하는 과정을 서술한 코드이다.
{{{#!syntax java
percolateDown(A[], k):
child ← 2k+1
right ← 2k+2
if (child ≤ n-1)
if (right ≤ n-1 and A[child] < A[right])
child ← right
if (A[k] < A[child])
A[k] ↔ A[child]
percolateDown(A, child)
}}}
다음은 배열 A[0…n-1]을 힙으로 만드는 과정을 서술한 코드이다.
{{{#!syntax java
buildHeap(A[]):
for i ← (n-2)/2 downto 0
percolateDown(A, i)
}}}
다음은 힙에서 원소를 삭제하는 과정을 서술한 코드이다. 힙에서 최대 원소를 리턴하고 삭제하여 힙의 크기를 하나 줄인다. 이 방법은 맨 위의 노드를 최소 원소로 대체한 뒤 스며내리기하는 과정으로 이루어진다.
{{{#!syntax java
deleteMax(A[]):
max ← A[0]
A[0] ← A[n-1]
n--
percolateDown(A,0)
return Max
}}}
====정렬 의사 코드====
다음은 힙 정렬을 서술한 코드이다. 앞에서 힙을 만드느라 고생한 덕으로, 힙 정렬의 의사 코드는 의미 파악이 어렵지 않다.
{{{#!syntax java
heapSort(A[]):
buildHeap()
for i ← n-1 downto 1
A[i] ← deleteMax(A)
}}}
====분석====
heapSort의 for 루프는 n-1번 순환하고, 각 순환에서 시간을 좌우하는 deleteMax()는 충분히 잡아도 [math(O(\log n))]이다. 힙 구성을 담당하는 buildHeap()에 소요되는 시간은 [math(\Theta(n))]이다. (이는 하위 문단에 자세히 서술한다.) 그러므로 힙 정렬의 총 수행 시간은 [math(O(n\log n))]이고, 힙 정렬은 비교 기반 정렬이므로 [math(\Theta(n\log n))]가 된다.
=====힙 구성의 증명=====
percolateDown()은 해당 서브 트리의 높이가 시간을 좌우하는데, 어떤 서브 트리도 높이가 [math(\log_{2} n)]을 넘지 않으므로 percolateDown()을 한번 수행하는데 [math(O(\log n))]이 소요된다. buildHeap()에서 percolateDown()을 호출하는 횟수는 ⌊n/2⌋이므로 전체적으로 --단순하게 곱한다면-- [math(O(n\log n))]이 된다. 그러나 모든 percolateDown()의 시간을 [math(O(\log n))]으로 잡은 것은 다소 지나치다. 맨 처음 호출되는 percolateDown()의 입력 트리는 고작 한 단계의 작업만 하면 되는데, 이런 것들이 꽤 여러 개 있다. 위로 올라갈수록 높이가 높은 서브 트리의 수는 줄어든다. 이 경우의 수들을 합산하면 [math(O(n\log n))]가 아닌 [math(\Theta(n))]이 된다. 이것을 자세히 증명해보자.
percolateDown()은 힙의 높이에 비례하는 시간이 소요된다. 즉, 힙의 높이가 h라면 [math(O(h))]의 시간이 소요된다. 원소의 수가 총 [math(n)]인 힙의 높이는 [math(\log_{2} n)]이다. 높이가 [math(h)]인 트리의 노드 수는 기껏해야 [math(⌈\frac{n}{2^{h+1}}⌉)]이다. 따라서 buildHeap()의 수행 시간은 다음과 같다.
[math(\sum_{h=0}^ {⌊\log_{2} n⌋} ⌈\frac{n}{2^{h+1}}⌉O(h)=O(n \sum_{h=0}^ {⌊\log_{2} n⌋} \frac{h}{2^{h+1}})=O(n))]
마지막 단계는 [math(\sum_{h=0}^ {⌊\log_{2} n⌋} \frac{h}{2^{h+1}})]가 2보다 크지 않기 때문이다. 임의의 [math(k)]에 관해 [math(S_{k}=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+…+\frac{k}{2^k})]라 하면 [math(2S_{k}=1+\frac{2}{2^1}+\frac{3}{2^2}+…+\frac{k}{2^{k-1}})]이고 [math(2S_{k}-S_{k}=S_{k}=1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+…+\frac{1}{2^{k-1}}-\frac{k}{2^k} \leq 2 - \frac{k}{2^k} \leq 2)]이다.
