[알고리즘] Inplace-Quick sort 이론 간략 정리

추가 공간을 일반 퀵소트보다 줄이는 알고리즘

 

추가 공간: $O(n)$->$O(1)$( 재귀적일때는 $O(lgn)$을 사용)

 

전략은 이전 퀵소트와 같이, 분할 정복을 이용할 것이다.

다만 공간을 추가적으로 사용하지않고, 해야하므로, 요소끼리 스위칭하는 방식으로 해야한다.

 

 

In-place Quick sort 수도코드:

Algorithm inPlaceQuickSort S, l, r
	Input sequence S , ranks l and r
	Output sequence S with the
		elements of rank between l and r
		rearranged in increasing order
	if l >= r
		return
	i <- a random integer between l and r // pivot index
	x <- S.elemAtRank(i) //pivot
	(h, k) <- inPlacePartition(x) // divide & conquer
	inPlaceQuickSort(S, l, h - 1) // recursive(left - L)
	inPlaceQuickSort(S, k + 1, r) // recursive(right - E U G)

 

알고리즘:

인덱스 j, k 를 sequence 각 양끝에 설정하고,

시퀀스 안에서 랜덤으로 pivot을 정해 뽑은 후, p라고 할때

S[h] < p, S[k] >p 이면 계속 인덱스를 j= j + 1, k= k - 1 한다.

만약 조건이 성립하지 않는게 j , k 중 1개 나오면, 다른 나머지도 성립하지 않을때까지 이동.

이동 후에 그 둘의 위치를 swap하고, 다시 인덱스를 이동하면서 pivot과 값을 비교

이를 j = k가 될때까지 반복한다.

강의자료 참조

예시 코드

Algorithm inPlacePartition(x)
	Input pivot x
    	Output index h, k
    h <- 0
    k <- S.size
    while h != k
   	if S[h] < x
    		h <- h+1
        if S[k] >= x
        	k <- k-1
        if S[h] >= x and S[k] < x
        	temp <- S[h]
            	S[h] <- S[k]
           	S[k] <- temp //swap
    return (h,k)

이렇게 되면, $L$과 $E\cup G$의 형태로 분할과 동시에 정렬할 수 있다.

(L: pivot보다 작은 그룹, EUG: pivot과 같거나 큰 그룹)

파티션을 나누는 과정에서 pivot은 정렬이 되었다고 볼 수 있기 때문에

재귀적으로 호출하게 되면, 분할정복이 가능해진다.

(시퀀스 요소가 1개면 정렬이 되었다고 볼수 있기 때문)