max(min) sort 보다 빠른quick select

N개의 숫자 배열이 존재할때

상위 또는 하위 k를 선택하는 알고리즘으로 많이 알려진

max sort를 사용한다.

max heap sort는 average case에 대해 O( nLOGm )정도의 시간 복잡도를 가지는데

이것보다 빠른 quick select라는 방법론이 있어서 간단히 소개한다.( average case 에 O(n) )

우선 배열에 아래와 같이 10개의 값이 존재한다고 할때

v[10] = {5, 3, 8, 9, 6, 0, 7, 1, 4, 2}

Quick Sort에서 pivot을 선정하고 pivot을 기준으로 좌측에는 피봇보다 작은 값을 우측에는 큰값을 놓게 된다.

이를 구간을 잘게 쪼개 반복적으로 실행하게 되는데

quick select는 이 방법을 이용해 다음과 같이 처리한다.

최초의 pivot을 배열의 마지막 값( v[9] )으로 하고

pivot보다 작은 값(2)이 나올때까지 배열을 스캔하다( 배열 0~8 까지 체크 )

피봇보다 작은 값이 발견되면 swap한다( swap은 save point라는 것을 하나 두고 그것과 스왑을 하는데 save point는 스왑이후 하나씩 증가한다. )

v[10] = {5, 3, 8, 9, 6, 0, 7, 1, 4, 2}

피봇보다 작은 값 v[5] = 0

초기 save point는 0 , v[0] = 5

이 두개의 값을 서로 교환한다.

{5, 3, 8, 9, 6, 0, 7, 1, 4, 2} 교환

{0, 3, 8, 9, 6, 5, 7, 1, 4, 2}  save point = 1로 하나 증가시킴

쭉 검사를 하면 v[7]에 와서 위와 같은 과정을 한번더 거친다.

save point가 1이므로

swap( v[1], v[7] )을 하고

{0, 1, 8, 9, 6, 5, 7, 3, 4, 2}  save point = 2

v[8]까지 검사가 완료되면

최종적으로 피봇을 현재의 save point와 swap하게 된다.

swap( v[8], v[2] )

{0, 1, 2, 9, 6, 5, 7, 3, 4, 8}

다음 iteration에서는

save point를 기준으로 좌,우를 나눠서 진행( recursive )하게 된다.

찾고자하는 min(max)의 개수를 k라고 하고

save pointer를 sp라고 할때

a> sp < k  이면  배열을 st부터 끝가지로 가정하고 위의 내용을 반복하다( 여기서 k 값은 k-sp 가 된다. )

b> sp > k  이면  배열을 0 부터 st까지로 가정하고 위의 내용을 반복한다.( 여기서 k 값은 그대로 k이다. )

위에서 설명한 내용까지 배열의 상태를 보면 아래와 같은데

{0, 1, 2, 9, 6, 5, 7, 3, 4, 8}

sp 는 2이고 k값은 3이기 때문에 sp(2) < k(3)

b>의 과정을 수행한다.

즉 0~10까지인 배열중에 

sp에서 배열의 마지막까지가 넘어간다. { 2 9 6 5 7 3 4 8 }

    

우리가 원하는 값이 작은값 3개일때 피봇이 해당 위치에 오는 순간 재귀호출은 종료된다.

피봇아래는 피봇보다 작은 값을 보장한다( 정렬되지 않음 )

v[5]=0 v[0]=5   5 3 8 9 6 0 7 1 4 2     pivot=2

v[7]=1 v[1]=3   0 3 8 9 6 5 7 1 4 2     pivot=2

v[9]=2 v[2]=8   0 1 8 9 6 5 7 3 4 2     pivot=-1

v[0]=2 v[0]=2   2 9 6 5 7 3 4 8 pivot=8

v[2]=6 v[1]=9   2 9 6 5 7 3 4 8 pivot=8

v[3]=5 v[2]=9   2 6 9 5 7 3 4 8 pivot=8

v[4]=7 v[3]=9   2 6 5 9 7 3 4 8 pivot=8

v[5]=3 v[4]=9   2 6 5 7 9 3 4 8 pivot=8

v[6]=4 v[5]=9   2 6 5 7 3 9 4 8 pivot=8

v[7]=8 v[6]=9   2 6 5 7 3 4 9 8 pivot=-1

v[0]=2 v[0]=2   2 6 5 7 3 4     pivot=4

v[4]=3 v[1]=6   2 6 5 7 3 4     pivot=4

v[5]=4 v[2]=5   2 3 5 7 6 4     pivot=-1

v[0]=2 v[0]=2   2 3     pivot=3

v[1]=3 v[1]=3   2 3     pivot=-1

v[-1]=0 v[-1]=0 0 1 2 3 4 7 6 5 8 9     pivot=-1

예제 코드가 있는 페이지 : http://rosettacode.org/wiki/Quickselect_algorithm