[[분류:정보]] ==개요== 이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다. 어떤 항목들을 정렬하는 알고리즘으로, 매우 다양한 방법과 시간복잡도를 가진다. 배열뿐만 아니라 힙과 같은 트리 구조 등을 사용할 수 있다. 분석에 관해서는 [[시간 복잡도]] 문서 참고. ==기초적인 정렬 알고리즘== ===선택 정렬(Selection Sort)=== 가장 작은(또는 큰) 원소를 찾아 맨 앞(또는 뒤)의 원소와 교환하는 과정을 반복하여 전체를 정렬하는 방식이다. 본 문서에서는 가장 큰 원소를 찾는 것을 기준으로 서술한다. ====의사 코드==== 다음은 선택 정렬의 의미를 간이화하여 서술한 코드이다. {{{#!syntax java selectionSort(A[], n): for last ← n-1 downto 1 A[0…last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] }}} 다음은 의사코드 1에서 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다. {{{#!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\log n))]라는 것을 알 수 있다. * '''평균적인 경우''': 크기 [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)=== 힙 자료구조를 이용해 데이터를 정렬하는 알고리즘으로, 배열을 최대 힙(또는 최소 힙)으로 만든 뒤, 루트(가장 크거나 작은 값)를 배열의 마지막 요소와 교환하고 힙 크기를 줄이는 과정을 반복하는 알고리즘이다. 본 문서에서는 가장 큰 원소 맨 위의 노드에 삽입하는 것을 기준으로 서술한다. ===셸 정렬(Shell Sort)=== 삽입 정렬의 단점을 보완한 알고리즘으로, 처음에는 큰 간격으로 데이터를 나눠 부분 정렬을 하고, 간격을 점점 줄여가며 최종적으로는 전체 데이터를 효율적으로 정렬하는 알고리즘이다.
