공부/알고리즘2011. 7. 3. 01:08



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


Posted by skyjumps