퀵소트(Quick Sort)의 가장 핵심적인 것은 피벗 엘리먼트(Pivot Element)와 파티션 프로시저(Partition Procedure)이다. 피벗을 선택하고, 피벗 요소가 마지막으로 남을 때까지 계속해서 파티션을 하는 것이 전부이다. Quick Sort의 최악의 경우는 n^2이지만, 평균 수행 시간은 대단히 효율적이다. 퀵소트는 in-place 정렬이 가능한 알고리즘이다.
병합 정렬(Merge Sort)의 대략적인 흐름은 다음과 같다.
Mergesort(begin, end)
{
mergesort(begin, mid)
mergesort(mid, end)
merge(begin, end)
}
따라서, w(n) = w(n / 2) + w(n / 2) + Θ(n) = 2W(n / 2) + Θ(n)이며, Master Theorem을 사용해서 이 점화식을 풀어 낼 수 있다. Θ(n)은 각각의 정렬된 결과를 병합(merge)하는데 소모되는 시간이다. 병합 정렬은 분할 정복 기법(Divide and Conquer)을 아주 잘 이용한다. 직관적으로 설명하면 다음과 같다.
분할 : 정렬할 n개 원소의 수열을 n / 2개씩 두 개의 부분 수열로 분할한다.
정복 : 병합 정렬을 이용해서 되부름으로 그 두 부분 수열을 정렬한다.
결합 : 정렬된 두 개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다.
정렬할 수열의 크기가 1이 되면 그것은 이미 정렬된 것이므로 더 이상 할 일이 없게 되고, 따라서 되부름 호출은 '바닥에 이르게' 된다.
병합 정렬 알고리즘에서 핵심적인 작업은 '결합' 단계에서 정렬된 두 부분 수열을 병합하는 것이다. 병합을 하기 위해 보조 프로시저 Merge(A, p, q, r)이 필요한데, 여기서 A는 배열이고 p, q, r은 인덱스로서 p ≤ q ≤ r을 만족한다. 프로시저 Merge는 두 부분 배열 A[p..q]와 A[q + 1..r]이 정렬되어 있다고 가정하고 이들을 병합해서 하나의 정렬된 배열을 만드는데, 이것이 원래의 부분 배열 A[p..r]을 대체하게 된다.
Reference
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithm Second Edition, The MIT Press
문병로, 심규석, 이충세 역, Introduction to Algorithm Second Edition, 한빛미디어
병합 정렬(Merge Sort)의 대략적인 흐름은 다음과 같다.
Mergesort(begin, end)
{
mergesort(begin, mid)
mergesort(mid, end)
merge(begin, end)
}
따라서, w(n) = w(n / 2) + w(n / 2) + Θ(n) = 2W(n / 2) + Θ(n)이며, Master Theorem을 사용해서 이 점화식을 풀어 낼 수 있다. Θ(n)은 각각의 정렬된 결과를 병합(merge)하는데 소모되는 시간이다. 병합 정렬은 분할 정복 기법(Divide and Conquer)을 아주 잘 이용한다. 직관적으로 설명하면 다음과 같다.
분할 : 정렬할 n개 원소의 수열을 n / 2개씩 두 개의 부분 수열로 분할한다.
정복 : 병합 정렬을 이용해서 되부름으로 그 두 부분 수열을 정렬한다.
결합 : 정렬된 두 개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다.
정렬할 수열의 크기가 1이 되면 그것은 이미 정렬된 것이므로 더 이상 할 일이 없게 되고, 따라서 되부름 호출은 '바닥에 이르게' 된다.
병합 정렬 알고리즘에서 핵심적인 작업은 '결합' 단계에서 정렬된 두 부분 수열을 병합하는 것이다. 병합을 하기 위해 보조 프로시저 Merge(A, p, q, r)이 필요한데, 여기서 A는 배열이고 p, q, r은 인덱스로서 p ≤ q ≤ r을 만족한다. 프로시저 Merge는 두 부분 배열 A[p..q]와 A[q + 1..r]이 정렬되어 있다고 가정하고 이들을 병합해서 하나의 정렬된 배열을 만드는데, 이것이 원래의 부분 배열 A[p..r]을 대체하게 된다.
Reference
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithm Second Edition, The MIT Press
문병로, 심규석, 이충세 역, Introduction to Algorithm Second Edition, 한빛미디어