분할정복법
분할 : 배열이 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.
lower part 의 element ≤ upper part의 element
피봇보다 작은 값 <<<< 피봇보다 큰 값
정복 : 각 부분을 순환 정렬한다.
합병 : 암것도 할게 없다
예시로
n개의 데이터를 피봇으로 선정 한 뒤
피봇보다 작은 값 <<<< 피봇 >>> 피봇보다 큰 값
이런 식으로 정렬한다.
그래서 1/2n개 이런 식으로 나눠지진 않음
n = n-1 + o
n = o + n-1 이런 식으로 균일하지 않게 나눠질 수 있음.
Quicksort
- 정렬한 배열이 주어짐. 마지막 수를 기준(pivot)으로 삼는다.
- 기준보다 작은 수는 기준의 왼쪽에, 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다.
- 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다. (정렬 완료)
따라서 여기서는 분할 시에 partition 이 중요하다!
수도 코드
quicksort(A[], p, r){
if(p<r) then{
//q가 피봇의 위치임
q = partition(A, p, r); //분할
quicksort(A, p, q-1); //왼쪽 부분배열 정렬
quicksort(A, q+1, r); //오른쪽 부분배열 정렬
}
}
partition(A[], p,r){
배열 A[p...r]의 원소들을 A[r] 기준으로 양쪽으로 재배치하고
A[r]이 자리한 위치를 return 한다.
if A[j]≥x
j <- j+1;
else
i <- i + 1;
exchange A[i] and A[j];
j <- j+1;
}
파티션을 하기 위해서 무조건 피벗하고 비교를 하는 작업이 필요하다
Partition(A, p, r){
x <- A[r];
i <- p-1;
for j<-p to r-1
if A[j] ≤ x then
i < i+1;
exchange A[i] and A[j];
exchange A[i+1] and A[r];
return i+1; //다시 위치 리턴
}
데이터가 n개니까 전부 비교해야 해서 O(n) 의 시간 복잡도를 가진다.
그런데 최악의 경우
항상 한 쪽은 0개, 한쪽은 n-1개의 경우로 분할되는 경우에는
이미 데이터가 정렬 되어 있을 경우에 발생한다.
이거는 마지막 원소를 피벗으로 선택하는 경우인데,
어짜피 정렬이 되어 있는 n-1개를 recursion으로 정렬하는 것인데
recursion을 돌렸을 때도 계속 마지막 원소를 피벗으로 선택한다면
0 + n-1 + n
= n-1 + n
= n-2 + n-1 + n -1 + n
이런 식으로 진행이 되어서 O(n^2)의 (= n(n-1)/2) 시간 복잡도를 가진다.
그러나 최선의 경우에는
항상 절반으로 분할되어서
T(n) = 2T(n/2) + O(n)
= O(nlogn)의 시간 복잡도를 가진다.
보통 quick이므로 이름을 저렇게 붙였지만
최악의 경우에는 n^2일 수 있다.
Balanced Partition - 항상 한쪽이 1/9 이상이 되도록 분할된다면?
어쨌든 nlogn 의 속도를 가질 수 있다.
평균 시간복잡도
평균 = 기대값
P(I) : I가 입력으로 들어올 확률
T(I) : I를 정렬하는데 걸리는 시간
일 때 P(I)를 모른다면
P(I)에 관한 적절한 가정을 한 후 분석
예 : 모든 입력 인스턴스가 동일한 확률을 가진다면
P(I) = 1/n!
어려우나 위의 이론과 같이 이러저러 섞여 있을 경우
O(nlog2n)을 가진다는 말인가 보다.
Pivot의 선택
- 첫번째 값이나 마지막 값을 피봇으로 선택
: 이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
: 현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매우 높음
: 따라서 좋은 방법이락 ㅗ할 수 없음
-Median of Three
: 첫 번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 피봇으로 선택
: 최악의 경우 시간복잡도가 달라지지는 않음
- Randomized QuickSort
: 피봇을 랜덤하게 선택
: no worst case instance ,but worst case execution
: 평균 시간복잡도 O(nlogn)
댓글
댓글 쓰기