In-Place Quick Sort

먼저 포스팅한 내용에서는 Quick Sort를 정리했다.
하지만 Quick sort는 매번 다른 그룹들을 만들어 공간 복잡도를 낭비하는 성향이 있다.
이를 효율적으로 개선한 In-Place Quick Sort가 있다.

1) In-Plcae란
알고리즘이 O(1) space 즉, 상수개의 공간을 사용하는 방식이다.
이때 재귀적으로 알고리즘을 수행하는 경우 O(log N)만큼의 복잡도는 허용된다.

2) 구현
먼저 배열에서 pivot을 정하는건 비슷하다.
pivot을 정하고 가장 왼쪽에는 j 가장 오른쪽에는 k 인덱스라고 정의한다.
1) j인덱스는 +1씩하며 pivot보다 크거나 같은 값을 발견할때까지 오른쪽으로 이동한다.
2) k인덱스는 -1씩하며 pivot보다 작은 값을 발견할때까지 왼쪽으로 이동한다.
3) j와 k인덱스를 서로 교환한다.
위 과정을 j인덱스와 k인덱스가 만날때까지 반복한다. 그러면 적어도 pivot의 왼쪽에는 pivot보다 작은 그룹 오른쪽에는 pivot보다 큰 그룹이 된다. 위 과정을 작은 그룹, 큰 그룹에서 반복한다.

3) 결과
Quick Sort와 시간복잡도는 동일하지만 공간복잡도는 훨씬 좋아진다.
따라서 메모리가 부족한경우 위의 In-Place Quick sort로 구현하는게 좋다.