[COSE214] Sort: Merge Sort, Quick Sort

Divide&Conquer approach로 알고리즘을 디자인 하는 방법에 대해서 서술하시오. 

 

Divide&Conquer 접근은 문제를 나눌 수 없을 때까지 나누어서 각각을 푼 후 다시 합병하여 문제의 답을 얻는 알고리즘이다. 이는 1) Divide 단계에서 문제를 더 이상 나눌 수 없을 때까지 분할하여 작은 부분문제들을 만든다. 2) Conquer 단계에서 분할된 부분 문제를 재귀적으로 해결하며, 3) Combine 단계에서 분할된 부분 문제를 결합하여 최종 해결책을 도출한다. 

Divide&Conquer 원리를 이용한 알고리즘에는 대표적으로 merge sort, quick sort가 있다. 

 

<Merge Sort>

Merge Sort란 하나의 배열을 두 개의 균등한 크기로 분할하고, 두 부분을 합치면서 배열을 정렬하여 전체가 정렬된 배열이 되게 하는 방법이다.

merge sort pseudocode

 

<Quick Sort>

Quick Sort는 하나의 배열을 피벗을 기준으로 두 개의 비균등한 리스트로 분할하고, partition 함수를 이용해 pivot보다 큰 원소는 오른쪽에, pivot보다 작은 원소는 왼쪽에 위치하도록 분할한다. 그 후 분할된 부분 리스트를 정렬하기 위해 다시 퀵 정렬을 적용하여 분할된 부분 리스트를 다시 재귀적으로 정렬한다. 퀵 정렬 시 각 부분 리스트가 이미 정렬되어 있기 때문에 결합 단계는 필요하지 않다. 

퀵 정렬의 시간복잡도는 평균적으로 O(nlgn)인데 이는 리스트의 분할이 대체로 균등하게 분할되어, merge sort와 유사하게 상황이 발생하게 된다는 가정에 기반한다. 하지만 pivot을 리스트의 값 중 최대값이나 최솟값을 선택하게 되는 최악의 경우, 분할된 부분 리스트 중 하나가 항상 다른 부분 리스트보다 길어지는 불균형 분할이 이루어지게 된다. 따라서 O(n)만큼의 추가 연산이 필요해지므로 시간 복잡도가 O(n2)이 된다.

quicksort pseudocode

 

Randomized quicksort는 random sampling을 이용하여(Random permutation 아님) pivot을 하나 선정한다. 

 

시간복잡도 계산 - comparison 횟수를 indicator random variable을 이용해서 계산

Random sampling과 Random permutation의 차이는 무엇인가?

Random sampling은 주어진 집단 내에서 일부 항목을 무작위적으로 선택하는 것이고, Random permutation은 주어진 요소의 순서를 무작위적으로 바꿔서 배열이나 리스트의 순서를 랜덤하게 재배치하는 것을 말한다.