Stargazer

추가 공간을 일반 퀵소트보다 줄이는 알고리즘 추가 공간: $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

특징: Worst case에 대해서는 $O(n^2)$ 시간이지만, Average case 에 대해서는 $O(n\log n)$ 시간이 걸린다. 전략: Divide and Conquer(분할 정복): 큰 문제를 여러개의 작은 문제로 분할하여 재귀적으로 처리 후 합쳐서 해결하는 방법 *단계: 1. 분할: 작게 문제를 나눈다.(이때, 나눈 것도 해결전략이 동일한 문제여야한다.) 2. 정복: 재귀적으로 계속 작게 나누면서, 문제를 해결한다.(문제를 해결할 수 있는 가장 작은 단위 까지 나눔) 3. 조합: 해결한 문제들을 조합하여 원래 input에 대한 결과값을 리턴한다. * 분할 정복 알고리즘 수도 코드: solve(I) n=size(I) if(n