[Lecture 20] Sorting Analysis / 정렬 알고리즘 분석

#개요

이번 포스트에서는 정렬 알고리즘들의 시간 복잡도 / time complexity를 분석해보자

#Insertion Sort

이제 정렬 알고리즘 하나인 삽입 정렬에 대해 알아보자. 삽입 정렬 알고리즘이란 한 번에 한 개씩 적당한 위치를 찾아 삽입·배치하는 알고리즘이다. 배열 내 데이터를 순회하며 정렬이 필요한 요소를 적당한 위치에 삽입하는 알고리즘이다. 즉 새로운 데이터를 이미 정렬된 데이터들 사이의 적절한 자리에 집어넣는 정렬방식이다.

삽입 정렬 자바 코드:

public void insertionSort(T[] A) {

 int j;
 for (int p = 1; p < A.length; p++) {
 T temp = A[p];
 for (j = p; j > 0 && temp.compareTo(A[j-1]) < 0; j--)
 A[j] = A[j-1];
 A[j] = temp;
 }
}

#삽입 정렬 평균 비교 비용

N개 요소의 리스트를 가정할 때 삽입 정렬에는 (N^2)/4 + Θ(N) 비교 비용과 (N^2)/4 + Θ(N) 할당 비용이 필요하다.

 

처음에 K번째 위치에 있는 요소가 j 위치에서 끝난다고 가정하자. 여기서 j는 1에서 K 사이의 모든 정수가 될 수 있다. j의 최종 위치는 K – j + 1 비교가 필요하다. 따라서 평균적으로 K번째 요소를 배치하기 위한 비교 횟수는 다음과 같다:

그렇기에 N개의 요소가 있는 리스트에 대한 삽입 정렬의 평균 총 비용은 다음과 같다

#삽입 정렬 평균 할당 비용

할당에 대한 분석도 비교 비용 분석과 비슷하다, 단지 K번째 위치의 요소가 j 위치에서 끝날 경우 j는 1에서 K – j + 2 사이라는 점에서 차이가 있다. 요소가 움직이지 않는 경우는 할당이 발생하지 않는다는 점에서 비교 비용과는 다르다. 비교 비용과 같이 분석을 하면 평균 총 할당 수는 다음과 같다:

#삽입 정렬 Best Case, Average Case, Worst Case

Best Case: N – 1 비교와 할당 없음(리스트가 사전에 정렬 돼있는 경우)

Average Case: (N^2)/4 + Θ(N) 비교 비용과 (N^2)/4 + Θ(N) 할당 비용

Worst Case: (N^2)/2 + Θ(N) 비교 비용과 (N^2)/2 + Θ(N) 할당 비용

#정렬 비용의 하한 (Lower Bound)

삽입 정렬을 개선하는 방법을 보기 전에 다음 질문을 한번 해보자: 정렬을 얼마나 빠르게 할 수 있을까?
여기서 "빠른"은 시간이 아니라 알고리즘의 복잡성을 의미해야 한다. 우리는 리스트를 완전히 정렬하기 위해 정렬 알고리즘이 수행해야 하는 요소의 수를 봐야한다.

어떤 정렬 알고리즘도 N개의 요소 리스트를 정렬할 때 평균적으로 적어도 Θ(f(N)) 비교를 수행해야 하기 때문에 이것은 매우 광범위한 문제이다. 또한 상황에 맞는 정렬 알고리즘들이 있기 때문에 우리는 단순히 특정한 정렬 알고리즘을 고려할 수 없다.

#N개의 요소의 가능한 순서

잠깐 조합론스러운 문제를 한번 보자. N개의 별개의 객체들의 집합이 주어졌을 때, 그것들을 한 줄로 정렬하는 다른 방법들의 수는 N! (N 팩토리얼)이다. 

 

따라서 정렬 알고리즘은 최악의 경우 N!개의 가능한 결과 중 올바른 순서를 결정해야 한다.

 

만약 알고리즘이 두 요소를 비교해야 한다면, 비교의 결과는 최종 답으로서 특정 순서를 제거하고, "탐색"을 나머지 가능한 순서로 유도한다. 이진 트리를 사용하여 비교 정렬 프로세스를 나타낼 수 있다.

#Comparison Trees / 비교 트리

비교 트리는 이진 트리로, 각 내부 노드는 집합의 두 특정 요소의 비교를 나타내며, 간선(edge)은 해당 비교의 두 가지 가능한 결과를 나타낸다.

예를 들어, 집합 A = {a, b, c}에서 정렬 알고리즘을 실행하면 두 요소를 비교하는 것으로 시작한다 (어떤 두 가지 요소를 선택하는지는 중요하지 않으므로 임의로 선택된다):

#Lower Bound on Comparisons / 비교의 하한

Theorem: 키 비교(key comparison)를 사용하여 N개 항목의 리스트를 정렬하는 알고리즘은 최악의 경우 ⌈log(N!)⌉의 키 비교를 수행해야 하며, 평균적인 경우에는 log(N!) 키 비교를 수행해야 한다. 

 

증명: 알고리즘의 작동 여부는 비교 트리로 나타낼 수 있다. 그 트리에는 N!개의 가능한 답이 있어야 하기 때문에 N!개의 리프가 있어야 한다.

 

N! 리프가 있는 이진 트리의 레벨 수는 적어도 1 + ⌈log(N!)⌉를 가져야 한다는 것을 이전에 증명했다. 답이 비교 트리의 하단 레벨에 있는 리프에 해당하는 경우, 알고리즘은 적어도 ⌈log(N!)⌉ 내부 노드를 통과해야 하므로 적어도 ⌈log(N!)⌉ 비교를 수행해야 한다. 이 경우 worst case comparison의 하한을 증명한다. average case 하한의 증명도 거의 똑같다. QED.

#Stirling’s Formula / 스털링의 공식

평균 사례 하한인 log(N!) 비교는 다소 생소하고 좋진 않다. 스털링의 공식을 적용하여 이를 단순화할 수 있다.

또는 로그 형식으로 변환

스털링의 공식을 사용하고 base를 바꾸면 log(n!)은 다음과 같다:

따라서 log(n!)은 Θ(n log n)이 된다.

 

대부분의 경우 첫 번째 항만 중요하므로 정렬에서 비교의 하한이 nlog(n) 이라고 할 수 있다.

#Shell Sort

셸 정렬은 삽입 정렬을 개선한 것으로, 일정한 간격으로 부분 배열을 나누고, 각 부분 배열을 삽입하여 정렬하는 알고리즘이다. 삽입 정렬(Insert Sort)은 요소들을 한 칸씩 이동하며 비교하여 가장 거리가 먼 요소와 비교를 할 경우 이동이 많은 오버헤드가 발생한다. 이를 개선한 것이 쉘 정렬로, 기준 값에서 일정한 간격의 부분 배열로 나누고, 각 부분 배열을 삽입하여 정렬하는 알고리즘이다.

[네이버 지식백과 / 쉘 정렬] 

 

즉 간단하게 단계적으로 셸 정렬 알고리즘을 보면

• 요소가 단계 크기, h, 간격인 불연속 하위 리스트로 리스트를 분할한다.
• 삽입 정렬을 적용하여 각 하위 리스트 정렬
• h의 값을 줄이고 첫 두 단계를 반복하여 h가 1인 패스 후에 멈춘다.

최종 패스(h는 1)는 단순히 전체 리스트에 대한 삽입 정렬을 적용한 것이기 때문에 최종 결과는 정렬된 리스트가 된다.

 

셸 정렬 자바:

public void shellSort(T[] A) {
 int increment = A.length / 2;
 while (increment > 0) {

 for (int i = 0; i < A.length; i++) {
 int j = i;
 T temp = A[i];
 while ((j >= increment) &&
 (A[j-increment].compareTo(temp) > 0)) {
 A[j] = A[j - increment];
 j = j - increment;
 }
 A[j] = temp;
 }
 if (increment == 2)
 increment = 1;
 else
 increment = increment * 5 / 11;
 }
}

#Shell Sort 성능

셸 정렬에 대한 complexity는 무엇일까? 일반적으로 O(N^2)로 알려져 있지만. 정확하게는 아무도 모른다.

 

컴퓨터 과학자로 유명한 Donald Knuth는 두 개의 특정 단계 크기를 사용하면 셸 정렬에 O(N^(3/2)) 시간이 걸린다는 것을 보여준 바 있다. 그 두 특정 단계의 크기는 (16N/π)^1/3 과 1이다.

 

규칙에 따라 단계 크기를 선택하면 하위 리스트를 적절하게 혼합할 수 있다:

일반적으로, N의 큰 값의 경우, 위에 주어진 단계 크기 체계를 사용하면 셸 정렬은 약 O(N5/4)이다.

#Divide and Conquer / 분할 정복

분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다. 그 외에 오토마타에서도 top-down parser등의 개념을 위하여 이용된다. 어원은 제국주의 시절 유럽 식민제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분할통치에서 시작되었다.

 

분할 정복의 포괄적인 의미는 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식을 말한다. 더 자세히 말해 분할 정복이란 문제를 해결하기 쉽도록 먼저 작게 나누고(Divide), 각각의 작은 문제들의 답을 구한 뒤(Conquer), 도출한 답들을 통합(Combine)하여 전체 문제의 해를 찾는 알고리즘이다. 즉 분할과 정복을 통해 문제를 해결하는 알고리즘이다. 주어진 문제를 해결하기 위해 나눌 수 있는 가장 작은 단위의 문제로 나누고, 이 문제들을 풀어 답을 구한 뒤, 답들을 통합하여 전체 문제의 해를 찾는 방법이다. 복잡한 문제의 경우 작게 나누어 생각함으로써 문제의 해결을 용이하게 하고, 업무적으로는 병렬처리가 가능해 퍼포먼스를 높일 수 있다.
[네이버 지식백과 / 나무위키] 분할 정복

 

우리가 방금 알아본 셸 정렬이 바로 "분할 정복" 방법을 사용한 정렬 알고리즘이다. 즉, 큰 문제를 더 작은 부분(아마도 더 관리하기 쉬운 부분)으로 나누고 각 부분을 처리한 다음 어떻게든 개별 결과를 재조합하여 최종 해를 구한다. Shell Sort에서는 단계 크기를 1로 줄이고 하위 목록을 원래 목록 구조 내에 물리적으로 유지함으로써 재조합이 이루어진다. 셸 정렬은 연결된 목록보다 연속된 리스트에 더 적합하다. 그렇기 때문에 이 바로 다음에 나올 정렬법은 분할 정복 방법을 유지하지만 연결 리스트에 더 적합한 알고리즘인 Merge sort / 합병 정렬을 알아보자

#Merge Sort / 병합 정렬

Merge란 ‘조합한다’는 뜻이며 일정한 순서로 되어 있는 데이터를 조합해서 하나로 하는 일을 말한다. 예를 들면, 각 지점의 정보를 1개의 파일로 순서를 붙이는 것 등이다. 또 소트란 분류의 뜻이며, 정보항목을 미리 정해진 일정한 순서가 되도록 정리하는 일을 말한다. 그러므로 머지소트란 컴퓨터를 사용하여 파일의 조합에 의해 분류하는 방법을 말한다.예를 들면 하루 동안의 거래 전표를 고객별로 정해진 순서로 늘어놓아 카드나 테이프에 의해 분류하는 일 등을 말한다. 

 

그렇기에 Merge Sort / 합병 정렬 이란 주어진 데이터들을 몇 부분으로 분할한 다음 각각을 재귀적으로 정렬하고, 두 부분을 합쳐서 하나로 만드는 방법이다. 즉, 하나의 리스트를 정렬하기 위해서 해당 리스트를 n개의 서브리스트로 분할하여 각각을 정렬한 수, 정렬된 n개의 서브리스트로 합병시켜서 정렬시키는 방법을 말한다. 복잡도는 O(n log n)으로 비교적 좋은 편이나 내부 정렬로는 별로 사용하지 않고, 수행시간이 오래 걸려 주로 외부 정렬에 활용된다.

 

퀵 정렬(Quick Sort)와 같이 분할과 정복을 통해 두 개의 정렬된 배열을 합치며(merge) 더 커진 배열로 만들어 간다.두 개의 그룹으로 나누어 정렬 후 병합한다는 점에서 퀵 정렬과 유사하지만 퀵 정렬은 좌우 두 배열의 크기가 다를 수 있어 이것이 최악의 성능 O(n^2)이 될 수 있으나, 병합 정렬은 좌우 두 배열의 크기가 항상 동일하게 분할되어 최악의 경우에도 O(nlogn)의 시간복잡도를 가진다는 점에서 차이가 있다. 또한 병합 정렬은 두 개의 배열을 합쳐 새로운 배열로 만들기 위한 별도의 임시 기억 장소가 필요하다.

[네이버 지식백과] 

 

위에서 언급했듯이 합병 정렬에서 우리는 리스트를 가능한 한 거의 동일한 크기의 두 개 이상의 하위 목록으로 잘라내고, 각 하위 리스트를 개별적으로 정렬한 다음, 정렬된 하위 리스트를 병합하여 원래 리스트의 정렬된 최종 결과를 얻는다. 

두 개의 정렬된 목록을 하나의 정렬된 목록으로 병합하는 것은 비교적 간단한 작업이다.

합병 정렬은 stable 정렬 알고리즘이다

#Merge Sort / 병합 정렬 성능

Merge sort 구현은 각각 대표되는 분할과 병합 함수 이 두 가지를 포함한다. 분할 단계의 수는 병합 단계의 수와 같으며, 재귀 하강 중에 분할이 발생하고 호출이 다시 나올 때 재귀 상승 중에 병합된다. 요소의 개수가 8인 리스트에 대해 분할을 한번 해보자:

최대 레벨의 수는 ⌈log(N)⌉이다.

 

모든 요소 비교는 병합 단계에서 수행된다. 논리적으로, 우리는 알고리즘이 다음 단계로 진행하기 전에 각 레벨을 재결합하는 것이라고 생각할 수 있다.

따라서 하위 목록을 병합하려면 ⌈log(N)⌉의 패스가 필요하다. 각 패스에서 각 리스트 요소는 (최대) 하나의 비교에 사용되므로 패스당 요소 비교 수는 N이다. 따라서 병합 정렬에 대한 비교 횟수는 Θ(N⌈log(N)⌉)이다.

 

병합 정렬은 이론적으로 최적의 비교 횟수에 매우 근접하다. 더 면밀한 분석에 따르면 N개의 요소 목록의 경우 병합 정렬을 사용한 평균 요소 비교 수는 다음과 같다:

이론적 최소값은 다음과 같다:

연결 리스트에서 병합 정렬은, 거의 최적의 비교를 제공하고 요소 할당이 필요하지 않으며(비록 상당한 양의 포인터 조작이 있지만) 많은 양의 추가 저장 스토리지가 필요하지 않다.

연속된 리스트(contiguous list)의 경우, 병합 정렬은 하위 목록을 위해 Θ(N) 추가 저장소를 사용하거나, 적은 양의 추가 저장소와 병합을 달성하기 위해 상당히 복잡한 알고리즘을 사용해야 한다.

#Heap Sort / 힙 정렬

힙이란 최댓값과 최솟값을 쉽게 추출할 수 있는 완전 이진트리의 자료구조이다.

 

힙 정렬은 내부 정렬 알고리즘의 하나로, 주어진 데이터들을 힙 자료구조, 즉, 최대 힙 트리(Maximum Heap Tree)나 최소 힙 트리(Minimum Heap Tree)를 이용하여 정렬하는 알고리즘이다. 내림차순으로 정렬 시 최대 힙 트리로 구성하고, 오름차순으로 정렬 시 최소 힙 트리로 구성하여 자료를 추출할 수 있다. 더 자세히 말하면 주어진 데이터들을 집산의 조건을 만족하는 완전 이진 트리로 구성한 다음 그 루트 노드를 꺼내면 그것이 데이터 중 가장 큰 값을 가지는 것이 된다. 그 다음 나머지 데이터들에 대해 다시 집산을 구성하고 루트를 꺼내는 작업을 되풀이하면 결국 모든 데이터들이 크기 순서대로 정렬된다. 이는 평균적으로 O(n log n)의 시간 복잡도를 가진다.

 

간단히 힙 정렬 알고리즘이 어떻게 수행되는지 알아보자.

 

힙 정렬 수행 절차(내림차순)
· 완전이진 트리로 정렬할 요소들을 최대 힙 트리로 구성한다.
· 요소 하나씩 추출(삭제)하여 배열의 뒤부터 저장한다.
· 최댓값부터 삭제되며, 삭제되는 순서로 정렬된다.

최대 힙 트리 삽입 절차
· 새로운 요소의 삽입 시 힙의 마지막 노드(node)에 새로운 노드를 삽입한다.
· 새로운 노드를 기존 노드와 비교하여 더 크면 위치를 교환한다.
· 부모 노드부터 노드들이 내림차순으로 최대 힙 트리로 구성되면 교환 작업을 종료한다.

최대 힙 트리 삭제 절차
· 부모노드를 삭제한다.
· 삭제된 부모 노드에 힙의 마지막 노드를 이동시킨다.
· 노드들과 비교하여 최대 힙 트리를 재구성한다.

힙 정렬 성능
완전 이진트리의 최대 힙 재구성 시 트리 깊이만큼 수행하므로 O(logn)만큼의 수행시간이 소요되며, 최악 시간복잡도와 최선 시간복잡도 및 평균 시간복잡도가 모두 동일하다.

[네이버 지식백과] 힙 정렬

 

목록을 먼저 힙에 빌드한 다음 힙이 비워질 때까지 힙에서 루트 노드를 반복적으로 삭제하여 정렬할 수 있다. 삭제된 루트가 배열의 역순으로 저장되면 (최대 힙이 사용되는 경우) 오름차순으로 정렬된다.

public static void heapSort(Integer[] List, int Sz) {
 BinaryHeap<Integer> toSort = new BinaryHeap<Integer>(List, Sz);
 int Idx = Sz - 1;
 while ( !toSort.isEmpty() ) {
 List[Idx] = toSort.deleteMax();
 Idx--;
 }
}

힙 자료구조는 다음 포스트 참조

 

힙 구축에 대한 위 포스트에서 분석을 보면, 완전한 이진 트리의 레벨 k는 2^k개의 노드를 포함할 것이며, 이러한 노드들은 루트 레벨보다 낮은 k개의 레벨이다. 따라서 루트를 삭제할 때 스왑된 노드가 sift down 될 수 있는 최대 레벨 수는 해당 노드가 스왑된 레벨 수이다. 따라서 최악의 경우 모든 루트를 삭제하기 위해 다음과 같은 수의 비교가 필요하다:

일반적으로 힙 정렬을 사용하면 기본적으로 동일한 수의 요소 스왑이 필요하다

#Heap Sort / 힙 정렬 성능

이전 분석에서 힙을 구축하는 비용을 추가 분석에 추가하면 총 비교 수와 총 스왑 수는 다음과 같다:

보통 분석에 따르면 평균적으로 힙 정렬이 최악의 경우보다 훨씬 더 잘 수행되지는 않는다.

#QuickSort / 퀵 정렬

퀵 정렬(quick sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. [네이버 지식백과] 퀵 정렬

 

퀵 소트는 분할 정복 방식을 사용한다는 점에서 merge sort와 개념적으로 유사하다. 차이점은 파티셔닝이 수행되는 방식과 하위 리스트가 적절한 상대적 순서로 유지되므로 병합이 필요하지 않다는 것이다.

 

• QuickSort는 자연적으로 재귀적인 알고리즘이며, 각 단계는 다음을 포함한다:
  • 현재 하위 리스트에 대한 pivot(기준 키) 값 선택
  • 하위 목록을 두 개의 하위 리스트로 분할한다. 왼쪽은 pivot 값보다 작은 값만 포함하고 오른쪽은 pivot 값보다 크거나 같은 값만 포함한다
  • 결과의 각 하위 리스트를 재귀적으로 처리한다

#Pivot 값의 중요성

Pivot 값의 선택은 QuickSort의 성능에 매우 중요한 영향을 미친다. 분할 단계는 두 개의 동일한 하위 리스트를 생성하는 것이 이상적이다. 최악의 경우 파티셔닝 단계는 하나의 빈 하위 리스트를 생성 할 수 있다.

 

이론적으로 이상적인 pivot 값은 하위 리스트에 있는 값의 중앙값이다. 불행히도 중간 값을 찾는 것은 너무 비싸서 실용적이지 않다.

#Pivot 값 고르기

• 중간 값을 찾는 데 일반적으로 사용되는 대안은 다음과 같다
  • 일정한 위치(첫 번째, 가장 중간, 마지막 등)에서 값을 구한다
  • 첫 번째 값, 마지막 값과 가장 중앙 값 사이의 중앙값을 취한다
  • 세 개의 다른 값을 찾아 그 값의 중앙 값을 구한다

세 번째 방법은 좋은 성능을 보장하는 것이 아니라 두 개의 비어 있지 않은 하위 리스트를 보장하는 유일한 전략이기 때문에 나열된 전략 중 가장 좋다. (물론 세 개의 고유한 값을 찾을 수 없는 경우에는 이 방법이 작동하진 않지만, 현재 하위 리스트에서 고급 정렬을 필요로 하지 않으므로 빠른 스왑을 사용해 효율적으로 완료된다). pivot 값을 찾기 위해 위에서 주어진 각각의 전략은 Θ(1)의 비교 비용을 가진다.

#하위 리스트 분할

QuickSort를 반복할 때마다 하위 목록을 분할해야 하므로 파티셔닝, 즉 분할은 효율적으로 수행되어야 한다. 다행히도, 비교와 할당에서 비용이 Θ(N)인 N개의 요소의 하위 리스트를 분할하기 위한 간단한 알고리즘이 있다.

template <typename T>
unsigned int Partition(T List[], unsigned int Lo, unsigned int Hi ) {
     T Pivot;
     unsigned int Idx,
     LastPreceder;
     Swap(List[Lo], List[(Lo + Hi)/2]); // take middle-most element as Pivot
     Pivot = List[Lo]; // move it to the front of the list
     LastPreceder = Lo;
     for (Idx = Lo + 1; Idx <= Hi; Idx++) {
     if (List[Idx] < Pivot) {
     LastPreceder++;
     Swap(List[LastPreceder], List[Idx]);
 		}
 	}
     Swap(List[Lo], List[LastPreceder]);
     return LastPreceder;
}

#퀵 정렬 구현

방금 설명한 pivot 과 파티션 / 분할 함수가 주어졌다고 가정하면, 주요 QuickSort 기능은 꽤나 간단하다.

template <typename T>
void QuickSort(T List[], unsigned int Lo, unsigned int Hi) {
 QuickSortHelper(List, Lo, Hi);
}
template <typename T>
void QuickSortHelper(T List[], unsigned int Lo, unsigned int Hi) {
 unsigned int PivotIndex;
 if (Lo < Hi) {
     PivotIndex = Partition(List, Lo, Hi);
     QuickSortHelper(List, Lo, PivotIndex - 1); // recurse on lower part,
     QuickSortHelper(List, PivotIndex + 1, Hi); // then on higher part
 }
}

#QuickSort / 퀵 정렬 성능

병합 정렬과 마찬가지로, 우리는 QuickSort를 pivot 선택과 각 중요하지 않은 하위 리스트의 분할을 포함하는 단계로 구성된 것으로 볼 수 있다. 각 단계의 총 파티셔닝 비용은 얼마일까? 위에서 구현된 바와 같이, 각 분할 단계는 pivot 값의 copy를 격리하고 해당 값은 이후에 이동되지 않으므로 각 단계에서 분할 대상 요소의 수가 감소한다. 그러나 어느 단계에서든 분할의 총 비용이 Θ(N)보다 나쁘지 않다는 것은 분명하다. 그러면 몇 단계를 수행해야 할까? pivot 값이 얼마나 잘 작동하는지에 따라 달라지는 문제가 있다. 

#퀵 정렬 성능 분석

• 분석의 단순성을 위해, 다음과 같은 가정을 하자:
  • 분할할 key 값은 1…N이다
  • C(N)은 길이 N 리스트에 적용할 때 QuickSort에서 수행한 비교 수이다
  • S(N)은 길이 N 리스트에 적용될 때 QuickSort에서 수행한 스왑 수이다

분할로 길이 r의 하위 리스트와 N – r – 1의 하위 리스트가 생성되는 경우, 다음과 같다

C(N) = N – 1 + C(r) + C(N – r – 1)

초기 파티션에는 N – 1 요소 비교가 필요하기 때문이다. 여기서 도출된 공식은 점화식 (recurrence relation)으로 알려져 있다. r의 주어진 값에 대해, C(N)에 대해 푸는 것이 가능하다.

#퀵 정렬 성능 Worst Case

r = 0, 즉 QuickSort가 하나의 빈 하위 목록을 생성하고 나머지 N-1 요소에서 pivot 값을 분할한다고 가정하자. 그러면 다음이 있다:

이것은 최악의 경우이며 selection sort의 최악의 경우만큼 나쁘다. 유사한 분석에 따르면 이 경우의 스왑 수는 다음과 같다:

이는 삽입 정렬보다 더 나쁜 Θ(1.5N^2) 요소 할당 비용이다.

#퀵 정렬 성능  Average Case

평균적인 경우, 우리는 분할 단계의 가능한 모든 결과를 고려하고 그것들의 평균을 계산할 것이다. 우리는 목록 요소의 모든 가능한 순서가 동일하게 정렬된 순서일 가능성이 있다고 가정하고 p가 선택된 pivot 값을 나타내도록 하자.
따라서 분할 후에는 키 값이 1…N이고, 값 1, …p – 1이 p의 왼쪽에 있고, 값 p + 1, …N이 p의 오른쪽에 있다고 가정하자.
길이 N인 리스트에서 QuickSort에 의해 수행된 평균 스왑 수를 S(N)으로 하고, 값 p를 초기 pivot으로 선택한 경우 S(N, p)를 평균 스왑 수로 하자. 여기에 제공된 분할 구현은 루프 내에서 p – 1 스왑을 수행하고 루프 외부에서 두 번 더 수행한다. 그러므로:

이제 p(1…N)에 대해 N개의 가능한 선택지가 있으며, 따라서 이 식을 p = 1에서 p = N까지 합하여 N으로 나누면 다음과 같은 결과를 얻을 수 있다:

이것은 또 다른 점화식이다. 우리는 교묘한 방법을 써서 이 문제를 해결할 수 있다. 먼저 QuickSort를 N-1 요소 목록에 적용하면 다음을 얻을 수 있다:

식 (A)의 양변에 N을 곱하고, 식 (B)의 양변에 N – 1을 곱한 다음 뺄셈을 하면 다음을 얻을 수 있다:

항을 재정렬 하면 다음을 얻는다:

이 점화식에 대한 패형(closed-form)의 해는 시퀀스의 처음 몇 개의 항을 적음로써 추측할 수 있다. 그렇게 함으로써, 우리는 다음을 얻는다

이제, 모든 N ≥ 1에 대하여,

이 사실을 방정식 (E)에 적용하면 다음과 같이 나타낼 수 있다:

Algebra 와 log base conversion을 사용하면 다음을 산출 한다:

비교에 대한 유사한 분석은 다음과 같은 관계에서 시작된다:

이것은 결국 다음을 산출한다:

따라서 평균적으로 QuickSort의 구현은 스왑과 비교 모두에서 Θ(N log N)이다.

#퀵 정렬 개선

• 퀵 정렬을 다음과 같은 변화를 주어 개선될 수 있다:
  • 비교적 짧은 하위 리스트에서 비재귀적 (반복적) 정렬 알고리즘으로 전환한다. 일반적으로 하위 리스트에 10개 미만의 요소가 포함된 경우 삽입 정렬로 전환하는 것이다.
  • 재귀를 완전히 제거하는 것. 그러나 결과 구현은 재귀 버전보다 이해하기 훨씬 더 어렵다 (따라서 검증하기도 까다롭다).
  • 주어진 구현에서 수행된 것보다 더 신중하게 pivot 값을 선택하기.
  • 파티션 / 분할 알고리즘을 개선하여 스왑 수를 줄인다. 분할 중 스왑 수를 주어진 구현에서 사용되는 스왑의 약 1/3로 줄일 수 있다.

이전의 정렬 알고리즘은 어쨌든 총 시간이 무시할 수 있는 짧은 목록에만 적합하다. MergeSort는 연속된 리스트에 적용할 수 있고 QuickSort는 연결 목록에 적용할 수 있지만, 각 적응은 상당한 효율성 및/또는 명확성 손실을 유도한다. 따라서MergeSort와 QuickSort는 실제로 경쟁자로 간주될 수 없다. 힙 정렬은 퀵 정렬의 평균적인 경우에 비해 열등하지만, 그다지 큰 차이는 나지 않는다. 최악의 경우, QuickSort는 여기서 논의되는 최악의 정렬 알고리즘 중 하나 이다. 그러한 관점에서 힙 정렬은 퀵 정렬의 최악의 동작에 대한 대비책으로서는 좋은 선택이다. 그러나 실제로 QuickSort는 최악의 경우로 전락하는 경우가 거의 없으며 거의 항상 Θ(N log N)이다.

# N log(N) 보다 빠른 정렬

이론적 분석에 따르면 어떤 정렬 알고리즘도 평균적인 경우에Θ(N log N)보다 더 적은 비교 / 복잡도가 있을 순 없다. 하지만, 이는 사실은 아니다. Θ(N log N)보다 더 적은 복잡도가 없다는 의견은 알고리즘이 키값을 비교함으로써 작동한다고 가정했기 때문이다. 하지만 리스트의 요소들을 서로 비교하지 않는 정렬 알고리즘이 존재한다. 이 경우 이전의 주장은 적용되지 않는다. 그러나 이러한 알고리즘은 정렬할 키 값의 유형 과/또는 범위와 관련된 특별한 가정을 필요로 한다. 이 알고리즘 들은 다음과 같다

#Bin Sort / Bucket sort / 버킷 정렬

버킷 정렬은 컴퓨터가 개발되기 전에 일련의 자료를 정렬하는 방법이었다. 일련의 자료를 조건에 따라 여러 "버킷"에 넣고 키 값에 따라 다시 정렬하는 것을 의미한다.

 

다음과 같은 0-99 범위의 정수 리스트를 정렬해야 한다고 가정해보자

34 16 83 76 40 72 38 80 89 87

저장을 위한 100(빈)의 정수 배열이 주어지면, 정수 리스트를 통과하고 각각의 값과 일치하는 빈에 배치한다

Bin[Souce[k]] = Source[k]

이 작업은 단 한번만의 패스가 필요하고 비교 하지 않아도 되기 때문에 비용이 N log(N)보다 훨씬 빠른 Θ(N)이다. 아마 정렬 알고리즘중에 Θ(N) 비용으로 실행 할 수 있는 알고리즘은 버킷 정렬 계열의 알고리즘들이 유일 할 것이다. 

function bucketSort(array, k) is
    buckets ← new array of k empty lists
    M ← 1 + the maximum key value in the array
    for i = 0 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 0 to k do 
        nextSort(buckets[i])
    return the concatenation of buckets[0], ...., buckets[k]

• 버킷 정렬의 단점:
  • 빈의 수는 값의 범위에 따라 결정된다
  • 정수 유사 값에만 사용가능하다

#Radix Sort / 기수 정렬

컴퓨터를 개발하기 전에 나타난 카드 분류기(card sorting machine)의 작동 원리를 이용한 정렬 방식. 즉, 수치자료의 정렬을 위한 방법으로, 숫자의 각 자릿수를 기준으로 정렬하는 알고리즘이다. 정렬할 요소를 여러 버킷에 분산하고 정렬하는 버킷 정렬의 일종이다. 기수에 따라서 요소를 버킷에 넣으므로 비교가 불필요하고 수치 자료의 각 자릿수만큼 반복한다.

 

내부 기억 장치를 사용하는 경우, 숫자를 정렬하기 위해서는 10개, 영문자이면 26개의 기억 영역(카드 분류기의 경우에는 포켓이라고 함)을 두고 여기에 정렬이 끝난 항목을 수용한다. 전체 항목이 각 부분 집합에 배분되면 부분 집합의 순으로 모으고, 다음 자리의 정렬에 착수한다. 이 조작을 차례로 반복하면 정렬이 끝나게 된다. 예를 들어 1번부터 99번까지 학생의 시험지를 순서 없이 거두어서 번호대로 정리한다면, 십 단위로 정렬하고 다시 1단위 순서로 각각 정렬하게 된다. 기수 정렬을 버킷 정렬(bucket sort) 이라고도 한다. 기수 정렬은 가장 상위 자릿수부터 정렬하는 MSD(most significant digit) 우선 정렬 또는 왼쪽 우선 정렬(left first sort)이라 하고, 가장 하위 자릿수부터 정렬하는 경우를 LSD(least significant digit) 우선 정렬 또는 오른쪽 우선 정렬(right first sort)이라고 한다.

 

기수 정렬 수행 절차
· 첫 번째 숫자를 키(key)로 해서 정렬 후, 해당 버킷에 분배한다.
· 버킷에 분배된 숫자를 차례대로 추출하여 두 번째 키를 적용하여 정렬 후 해당 버킷에 분배한다.
· 위의 과정을 키의 개수만큼 반복하며 정렬한다.

[네이버 지식백과] 기수 정렬]

 

0-99 범위의 정수 목록을 정렬해야 한다고 가정하자

34 16 83 76 40 72 38 80 89 87

저장할 10개의 연결 리스트(빈) 배열이 주어지면 정수 리스트를 통과한 다음 각각을 1의 자리 숫자와 일치하는 빈에 넣는다.

Bin
 0: 40 80
 1:
 2: 72
 3: 83
 4: 34
 5:
 6: 16 76
 7: 87
 8: 38
 9: 89

그런 다음, 각 빈을 순서대로 가져가서 두 번째 패스를 하고, 각 정수를 10의 자리 숫자와 일치하는 빈에 추가한다.

Bin
 0:
 1: 16
 2:
 3: 34 38
 4: 40
 5:
 6:
 7: 72 76
 8: 80 83 87 89
 9: