Divide-and-Conquer
(1) 피봇을 정하고 (2)피봇보다 작은 수 큰 수를 나누고 나눠진 집합에 대해 다시 (1),(2)번을 반복하면 정렬이 되는 그러한 정렬방식이다.
Partition
피봇을 정하고 피봇보다 작은 수 큰 수를 나누는 과정이다.
time은 Θ(n) 이다. 리스트 한번만 읽으면 되니까.
Balanced partitioning
파티션이 반반씩 나눠질때, T(n) <= 2T(n/2) + Θ(n) = O(nlgn)
퀵소트에서 피봇이 잘 뽑이면 이러한 결과가 나온다.
Unbalanced partitioning
피벗이 가장 작은 수나 가장 큰 수가 뽑혔을때
원소가 n개 있으면 파티션이 하나, n-1개로 나눠져서
최악의 경우가 된다. 파티션을 많이 해야 한다.
최악의 경우가 insertion sort랑 비슷하다.
T(n) = T(n-1) + Θ(n) 이므로 계산하면 Θ(n^2)가 된다.
worst cast 분석
unbalanced partitioning이 최악의 경우임을 보증하는가?
증명 여기 사이트 formal worst case analysis 참고
Average-case analysis
Zij = {zi, zi+1 ... zj} 인 array를 퀵소트한다고 하자.
X를 임의의 quicksort 실행에서 전체 비교횟수인 확률변수로 보면
quicksort의 평균수행시간은 O(n+E[X]). (n은 스캐닝 + etc)
각각 파티션마다의 비교횟수를 생각하지말고 전체적으로 비교횟수를 보자.
그러면 array에서 임의의 2개 원소는 많아야 한번 비교한다. 2개중 하나가 피봇일 때 한번 비교 하는 것이다. 그리고 피봇은 다음번 단계 이후부터는 비교대상에서 제외된다. 그래서 임의의 두개 원소는 기껏해야 한번 비교가 된다.
그럼 이 식들이 이해가 되었음.
계산과정은 생략하고
계산하면 O(nlgn)이 나온다. 평균수행시간이 된다.
Randomized quicksort
피벗을 랜덤으로 뽑는다.
average-case를 보장하도록 한다.
input의 형태에 관계없이 항상 uniform하게 quicksort를 할 수 있다.
'공부 > 알고리즘' 카테고리의 다른 글
11장 Hash Table (0) | 2011.07.08 |
---|---|
8장 Sorting in Linear Time (0) | 2011.07.03 |
Heapsort (1) | 2011.06.30 |
4 Recursion (0) | 2011.06.28 |
3장 Growth of Funtions (0) | 2011.06.24 |