퀵 소트 재귀 호출없이 구현하기

재귀의 장점은 프로그램이 간결하다는 장점이 있지만, 스택 메모리 오버플로우 가능성이 존재한다는 점과 프로그램 가독성이 떨어진다는 단점이 있다

 

[참고] https://www.geeksforgeeks.org/iterative-quick-sort/

 

재귀함수는 비재귀함수는 for, while 반복문으로 짤 수 있다. 퀵 소트를 구현하기 위해서는 quicksort 함수를 재귀함수로 이용했는데 stack 자료구조를 이용해 partition의 반환값을 비교해 아직 부분집합의 크기가 1보다 크다면 stack에 넣어 반복문을 수행시킬 수 있다

 

stack STL을 사용하는 것은 느리다. 배열로 대체하도록 한다