제자리 퀵 정렬

Alg inPlaceQuickSort(L,l,r)

if (l>=r)
	return
k <- l과 r 사이의 임의의 수 [pivot]
a,b <- inplacePartition(L,l,r,k)
inPlaceQuickSort(L,l,a-1)
inPlaceQuickSort(L,b+1,r)

 

<inPlacePartition>

1. 무작위로 피봇을 정한다.
2. 피봇을 맨 끝으로 보낸다.
3. 피봇과 나머지 배열 원소들과 크기 비교를 한다.
   1. 이 때 효율성을 높이기 위해서(?) 왼쪽에서 오른쪽으로만 탐색하는 것이 아니라, 왼쪽에서 오른쪽으로 탐색하는 것 하나(i), 오른쪽에서 왼쪽으로 탐색하는 것 하나(j) 이렇게 동시에 두 개가 탐색하도록 한다.
   2. 전제 조건: ( i≤j )
      1. 왼쪽 → 오른쪽 탐색: i
         1. A[i]가 피봇보다 작다면 i를 증가시키고(잘 정렬되어 있으므로 그 다음 단계로 넘어간다는 뜻)
         2. A[i]가 피봇보다 크다면 while문을 뛰쳐 나온다. (j와의 교환이 시급하다는 뜻)
      2. 오른쪽 → 왼쪽 탐색: j
         1. A[j]가 피봇보다 크다면 j를 감소시키고(잘 정렬되어 있으므로 그 다음 단계로 넘어간다는 뜻)
         2. A[j]가 피봇보다 작다면 while문을 뛰쳐 나온다.(i와의 교환이 시급하다는 뜻)
4. 교환을 해야 할 원소들끼리 교환을 한다.
   1. A[i] ↔ A[j]
5. i≤j 라면, 다시 3번 과정으로 돌아간다.
6. 모두 정렬이 끝나서 i를 기준으로 왼쪽은 피봇보다 작은 원소들이고 i를 포함한 오른쪽은 피봇보다 큰 원소들이 되었다면, r번째에 있는 피봇과 i번째에 있는 원소를 교환한다.
7. i를 리턴한다.