12. 퀵소트 피벗 선정 개선 [5 2주차]

12. 퀵소트 피벗 선정 개선 [5-2주차]

2024년 1월 13일 토요일

오후 10:08

<퀵소트 피벗 개선>

퀵소트에서 어떻게 최선의 피벗을 찾을 것인가?

 

중간값을 피벗으로 선택하면 배열이 1/2 로 나뉘어질 것이다.

따라서 중간값을 찾는 데 O(N)의 시간이 걸린다면, 퀵소트를 O(NlogN)시간에 수행할 수 있을 것이다.

 

Selection problem을 푼다면 중간값을 피벗으로 설정할 수 있다.

 

 

<The Selection Problem>

n개 중에 k번째로 작은 것을 찾는 문제.

정렬을 하면 O(NlogN) 시간에 풀 수 있다. 더 빠르게 할 수 있을까?

 

 

<The Approximate Median Problem>

정확한 중간이 아니라 대략적인 중간값을 찾는 문제. 정확히 중간값을 찾지 않고 일정 비율의 중간 근처 값을 찾아도 O(nlogn)시간에 퀵소트를 할 수 있다.

 

n개의 원소 중 rn ~ (1-r)n 등 안의 원소를 하나 찾는 문제이다.

• 0 < r < 1
• r = 0.3 으로 해 보자. 0.3n ~ 0.7n 등의 원소 찾기

 

 

<퀵소트 알고리즘을 활용한 selection>

퀵소트의 아이디어를 통해 selection을 풀 수 있을까?

 

 

퀵소트의 방식으로 배열을 분할하고 k등 원소가 존재하는 배열만 확인하면 된다.

 

퀵소트가 분할이 잘 된다면

n + n/2 + n/4 + … + 1 = 2n-1 시간이 걸린다.

 

 

<Selection 알고리즘>

 

1.     무작위로 피벗을 하나 골라, 퀵소트의 분할 및 피벗 기준 정렬을 수행한다. 이는 O(n) 시간이 걸린다.

2.     작은 원소가 있는 부분 배열의 원소 개수를 구한다. 여기에 1을 더한 값이 j라 하자. 그러면 피벗 원소는 j번째로 작은 원소이다.

3.     k==j 이면 피벗 원소를 리턴하면 된다.

k<j 이면 작은 원소들의 배열에 대해 재귀 호출,

k>j 이면 큰 원소들의 배열에 대해 재귀 호출한다.

 

문제점 : 피벗 원소가 가장 큰 값, 가장 작은 값이 선택되는 경우가 반복되면 n번 재귀 호출을 해야 한다. 1번 과정이 O(n) 시간이 걸리므로 최악의 경우 O(n²) 시간이 걸린다.

 

<Selection 알고리즘 개선>

 

 

1.     n개짜리 입력 배열을 원소 5개를 가진 n/5개 그룹으로 나눈다.

2.     각 그룹에서 중앙값을 찾는다. 중앙값이 n/5개 발견된다.

3.     Select를 재귀 호출하여, n/5개의 중앙값들에 대한 중앙값 x를 찾는다.

4.     x를 피벗으로 퀵소트 분할 과정을 수행한다.

 

5.     작은 원소 부분 배열의 크기 + 1 = j 라 하면, 피벗 원소는 j번째로 작은 원소이다.

6.     j == k 라면 x를 리턴. 그렇지 않으면 selection을 위와 같이 재귀적으로 호출

 

1은 O(n), 2는 O(n), 3은 T(n/5), 4는 O(n) 시간이 걸린다.

(5단계의 j값은 4를 끝내면 바로 구해진다)

 

6단계 재귀 호출에서, 시간이 얼마나 걸릴까?

 

 

<Selection 알고리즘 시간 복잡도>

 

x보다 큰 원소가 최소 몇 개 존재하는지 계산해 보자.

 

중앙값은 ⌈n/5⌉ 개이고, x보다 큰 중앙값은 ⌊ ( ⌈n/5⌉ / 2) ⌋ = L개이다.

 

중앙값이 x보다 큰 그룹 L-1개는 각각 5개의 원소를 가지고 있다.

(n이 5로 나누어떨어지지 않아서 원소 개수가 5보다 작은 그룹이 있을 수 있으므로 1을 뺀다)

각각의 그룹마다 중앙값보다 큰 원소가 2개씩 존재하므로, x보다 큰 원소는 총 3*(L-1)개 존재한다.

 

 

비슷한 논리로, x보다 작은 원소 수 또한 적어도 0.3n - 6개이다.

따라서 최악의 경우, select는 최대 0.7n + 6개에 대해 재귀적으로 호출된다.

 

따라서, 다음과 같은 점화식이 성립한다.

 

 

수학적 귀납법을 통해, 충분히 큰 상수 c에 대해

T(n) <= cn 이 성립한다는 것을 증명하자.

 

Base : n<140일 때, c가 충분히 크다면 부등식이 성립한다.

 

Step : k<n일 때, T(k) <= c*k이라고 가정하자.

140 <= n이라 하면

 

T(n) <= T(n/5 +1) + T(0.7n + 6) + an

      <= c(n/5 +1) + c(0.7n + 6) + an

        = 0.9cn + 7c + an

        = cn + (-0.1cn + 7c + an)

 

-0.1cn + 7c + an <=0 이라면 T(n) <= cn 이 성립한다.

위 부등식은

-cn + 70c + 10an <= 0

10an <= (n-70)c

과 같다. n>70일 때 부등식은

 

 

이다. n>=140 이므로 n/(n-70) <= 2 이다.

따라서 20a <= c 이기만 하면 위 부등식이 성립하고,

T(n) <= cn 이다.

 

따라서 Select의 시간 복잡도는 O(n)이다.

 

 

 

<selection을 이용한 피벗 선택의 한계>

O(n) selction을 이용해서 quicksort를 O(nlogn) 에 수행할 수 있게 되었다. 그러나 실제로 퀵소트 피벗 선택에 selection을 쓰지는 않는다. 알고리즘이 복잡해지면서 평균적으로 Merge Sort보다 느려지기 때문.