✨ 퀵 정렬 공간복잡도

퀵 정렬 알고리즘은 in-place 정렬이기 때문에 별도의 공간을 차지하지 않습니다

하지만 실제 퀵 정렬 알고리즘의 공간 복잡도는 O(log N) 또는 최악의 경우 O(N)입니다
그렇다면, 별도의 배열을 사용하지 않는데도 왜 공간복잡도가 O(1)이 아닐까요?

🤔 in-place 정렬인데 공간복잡도가 왜 생기지?

분할과 교환은 모두 배열 내에서 이뤄지기 때문에 추가적인 배열을 생성하지 않습니다

따라서 "퀵 정렬은 in-place 정렬이다" 라고 표현합니다
하지만 재귀 호출이 문제입니다

재귀 함수는 호출될 때마다 스택 메모리를 사용합니다
이 스택은 시스템 콜스택(Call Stack)에 쌓이며, 이는 공간복잡도에 영향을 줍니다

📚 퀵 정렬의 공간복잡도

퀵 정렬의 공간복잡도는 다음과 같이 나뉩니다:

경우	재귀 깊이	공간복잡도
평균	log N	O(log N)
최악	N	O(N)

📌 평균의 경우: O(log N)

피벗이 배열을 절반씩 잘 나눈다고 가정하면, 재귀 깊이는 log N 수준입니다
즉, 스택에 최대 log N 개의 호출이 쌓이며, 그에 따른 공간복잡도는 O(log N)입니다

📌 최악의 경우: O(N)

이미 정렬된 배열에 대해 항상 한쪽으로만 분할이 일어나면, 재귀 깊이는 N까지 늘어납니다
이런 경우엔 재귀가 선형적으로 호출되므로, 공간복잡도도 O(N)이 됩니다

✍️ 결론

퀵 정렬은 in-place 정렬이라 메모리 사용량이 적지만,
재귀 호출로 인한 스택 사용 때문에 공간복잡도가 O(1)은 아닙니다

평균적인 공간복잡도는 O(log N)이고 최악의 경우 O(N)입니다