Merge Sort, Quick Sort

Merge Sort

array를 반으로 자르고 반으로 잘린 array를 각각 정렬한 후 정렬된 값들을 합친다.

Divide and Conquer 접근법의 예.

 

Merge Sort

각각의 정렬에서 O(n)이 걸리고 정렬의 총 횟수는 logn이므로 O(nlogn)의 cost를 가지게 된다.

best, average, worst cases에서 모두 O(nlogn)의 cost를 가진다.

 

 

Quick Sort

Divide and Conquer 접근법을 사용하는 또다른 예이다.

 

array에서 기준이 되는 한 값을 선택한다(pivot 선택).

그리고 pivot을 기준으로 pivot보다 작은 값들은 pivot 왼쪽에 정렬하고, 큰 값들은 pivot 오른쪽에 정렬한다.(partition operation)

 

partition의 cost는 O(n)이 걸리게 된다.

 

QuickSort Example

QuickSort에서 Best Case는 항상 partition이 array의 반을 정확히 가르는 경우이다.

Worst Case는 그 반대로 pivot이 항상 제일 작거나 제일 클 때 일 것이다.

Average Case의 Cost는 다음과 같은 식으로 계산할 수 있다.

Average Case의 Cost 계산

위 식을 풀게되면 T(n) = O(nlogn)이 나오게 된다.

 

QuickSort optimization

Worst Case가 나오는 경우는 거의 없겠지만 Quick Sort의 성능을 높이기 위해서는 pivot을 잘 고르는 것이 중요하다.

pivot이 median에 가까울수록 성능이 더 좋을 것이다.

 

pivot을 고르는 방법은 여러가지가 있다.

가운데 위치한 pivot을 고르게 된다면 pivot을 고르는 시간은 줄어들지만 pivot이 median과 가깝지는 않을 것이다.

그렇다고 pivot을 median으로 고르게 되면 pivot을 고르는데 시간이 많이 소요된다.

절충안으로 내놓는 방법은 랜덤으로 k개의 원소를 뽑고 그 k개의 원소 중 median을 골라 그 값을 pivot으로 하는 것이다.

 

pivot을 고르는 방법 외에도 성능을 높일 수 있는 방법은 여러가지가 있다.

예를 들어 divide and conquer을 할 때 n이 작다면 quick sort를 하는 대신에 insertion sort나 selection sort를 하는 것이 더 효율적이다.

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업