pivot을 어떤걸 잡을 거냐? Selection을 해야 한다.
Selection: n개 중에 k등을 찾을 것
minimum, maximum (selection보다 쉬운 문제인듯)
median(중간값), selection
sorting을 했다면 selection은 쉬운 문제이지만 quick sort에서 중간값을 찾기위해 sorting한다??
sorting없이 selection할 수 있을까?
"k등이 x다" 만 알 수 있어야 한다.
x보다 작은 수, 큰 수는 알 수 있지만 이들사이에 누가 크고작은지 모른다 => 알면 그게 sorting한 것
sorting엔 nlog n 시간이 필요하다.
selection을 nlog n보다 작은 시간 안에 풀어야 한다. (아주 해피엔딩은 아닐 것임)
The Approximate Median Problem
대략 중간값 찾기
중간값은 퀵소트에서도, selection에서도 쓰면 좋다.
하지만 정확한 중간값이 필요한 것은 아님(annotation상으로 충분히 좋은 시간이 나옴)
등비수열에 의해 1/2이 아니라 1/4여도 O(nlog n)이기 때문에
0.3n등~0.7n등 => 가운데 40%
이 값을 pivot으로 쓰면되며, selection도 할 수 있다.
approximate median을 풀려면 selection을
selection을 풀려면 approximate median을 풀어야 함
두개 동시에 풀림?!
각각 따로 알고리즘이 있는 것이 아님?!
Selection Strategy with Approximate Median
selection을 퀵소트처럼 푸는 작전임 (pivot을 가지고!)
selection도 O(n^2)이 되는 것 아님? approximate median을 이용해서 풀거임
quicksort는 이 상태에서 왼쪽sorting 오른쪽 sorting
하지만 우리가 지금 찾으려는 것은 오직 k등
k가 왼쪽이면 k는 p보다 작을 것이고, k가 오른쪽이면 k는 p보다 클 것임
퀵소트는 양쪽 다 내려갔지만 selection은 둘중에 하나만 내려가면 됨!
한번에 pivot이 중간쯤위치한다면? O(n)
그렇지 않다면?머지보다 안좋음 O(n^2)
물론 평균은 O(n)이지만... worst의 경우를 피할 수 없다.
이제 approximate median등장! 이걸 어떻게 찾을 수 있는지 모른다.
approximate median을 찾았다고 치고 반으로 나눠 한쪽만 내려가자
S(n) = A(n) + n+ S(0.7n)
재귀로 아무리 크게 내려가도 0.7n (최악의 경우)
엄청나게 기발한 작전
1. n개 중 approximate median을 찾아라!
2. 무조건 5개씩 끊어라 (5의 배수라고 치고)
끊은 5개안에서 sorting해라
=> 1,2 합쳐서 여기까지 O(n)
5개 sorting한것을 세로로 정렬했다.
그 중에 중간만 모으고 그 중에 중간값(☆)
=> n/5개
왼쪽은 ☆보다 작고, 오른쪽은 ☆보다 크다.
홀수라고 가정하고 딱 중간이라고 생각하겠다! 짝수에도 가능
☆보다 작은 것은 전체의 몇개인가?
☆은 n/5개의 진짜 중간값!
따져보니 전체에서 최소 30%는 ☆보다 작음
최소 30%는 ☆보다 큼
☆는 중간 40%에 있다!
Analysis of Selection with A.M
S(n) = A(n) + n+ S(0.7n)
A(n) = n + S(0.2n)
서로가 서로를 불러쓰기 때문에 두 개는 동시에 풀린다.
두개를 합치면
S(n) = n + S(0.2n) + S(0.7n)
S(n) = an+b
an+b
= n +0.2an + 0.2b + 0.7an + 0.7b
= (1+0.9a)n + 0.9b
a=10, b=0
S(n)=10n, A(n)=3n이면 성립한다.
S(n) = A(n) = O(n)
worst case을 O(nlog n)으로 만들엇지만 결국 머지소트보다 느림
approximate median과 selection하면서 메모리할당을 이미 엄청 함..
selection은 노 해피엔딩..