[Introduction to Algorithms] 랜덤화된 퀵 정렬

 

1) 개요

- 퀵 정렬의 평균적인 경우를 살펴볼 때 모든 입력이 똑같은 확률로 발생한다고 가정했다.

  그러나 실제로는 이 가정이 언제나 들어맞지는 않는다.

  이 때, 알고리즘에 랜덤화 기법을 적용함으로써 모든 입력에 대해 성능의 기댓값을 높일 수 있다.

  때문에 입력이 충분히 큰 경우에는 정렬 알고리즘으로 랜덤화된 퀵 정렬을 많이 사용한다.

 

- 입력을 명시적으로 뒤섞음으로써 임의화를 할 수 있는데,

  이 같은 방법을 퀵 정렬에서도 적용할 수 있지만, 

  무작위 추출이라는 다른 랜덤화 기법을 사용하면 분석을 좀 더 간단히 할 수 있다. 

 

- 매번 A[r]을 기준으로 선택하는 대신 부분 배열 A[p...r]에서 임의의 원소를 선택하고

  이 원소와 A[r]을 교환한다.

  이렇게 기준 원소를 p, ... ,r 범위에서 무작위 추출하면 

  부분 배열에 있는 r-p+1개의 원소들 모두 동일한 확률로 기준 원소가 될 수 있다. 

  기준 원소를 임의로 선택하기 때문에 평균적으로 입력 배열을 상당히 균등하게

  분할할 수 있을 것으로 예상할 수 있다. 

 

- PARTITION과 QUICKSORT의 코드가 약간만 달라진다.

 새로운 분할 프로시저에서는 실제 분할 전에 교환하는 부분만 새롭게 추가된다.

RANDOMIZED-PARTITION(A, p, r)
i RANDOM(p, r)
A[r] <-> A[i]  // 교환
return PARTITION(A,p,r)

 

- 새로운 퀵 정렬은 PARTITION을 호출하는 대신 RANDOMIZED-PARTITION을 호출한다. 

 

RANDOMIZED-QUICKSORT(A, p, r)
if p < r
    q = RANDOMIZED-PARTITION(A, p, r)
    RANDOMIZED-QUICKSORT(A, p, q-1)
    RANDOMIZED-QUICKSORT(A, q+1, r)