퀵소트 문제

올려주신 퀵 소트 소스 코드를 보니 재귀를 이용하시는군요. 재귀 호출을 이용할 경우 내부적으로 스택이라는 메모리 공간을 사용하게 되는데, 0, 10000은 잘 되고 백만개는 스택 오버 플로우가 난다는 것으로 보아 스택이 부족한 것 같습니다. 일반적으로 VC++에서 윈도우 콘솔 응용 프로그램으로 작성하면 메모리를 원하는 만큼 쓸 수 있지만, 스택에 생성되는 지역 변수나 말씀하신 것과 같이 내부적으로 스택을 사용하는 작업의 경우 스택 자체의 크기가 한계가 있어 스택 오버 플로우 에러가 발생하기도 합니다.

즉, 질문자분의 경우 알고리즘 자체가 틀리지 않았다는 가정하에 스택 공간이 부족한 것이므로 별 다른 해법을 제시해드리기는 힘듭니다.

1. 퀵 소트를 재귀가 아닌 반복 버전으로 작성하시면 됩니다. 물론 이 경우도 스택과 비슷한 역할을 하는 메모리 공간을 사용해야 하지만 퀵 소트 특성상 묵시적으로 사용되는 스택의 양보다 훨씬 적은 메모리 공간만으로 구현할 수 있고, 무엇보다 heap 영역을 할당받아 스택처럼 사용할 수 있으므로 사실상 메모리 제한이 없다고 보시면 됩니다.

 

출처 : http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=67710813&qb=cXVpY2sgc29ydCDrqZTrqqjrpqw=&enc=utf8&section=kin&rank=16&search_sort=0&spq=0&sp=2