알고리즘

[알고리즘] Quick Sort

Quick Sort 정렬 알고리즘 중 하나로 분할 정복(Divide and Conquer) 전략을 사용하는 알고리즘이다. C++ algorithm 헤더에 있는 sort함수는 퀵 소트로 구현되어 있고, 이러한 이유는 평균 수행시간이 빠르기 때문이다. (수행 시간에 대한 분석은 아래에 정리할 것이다.) 퀵 소트에서 중요한 부분은 피벗(pivot)과 파티션(partition)이고, 간단하게 피벗을 뽑고 파티션한다! 라고 생각할 수 있다. 피벗은 비교를 진행하기 위한 기준이 되는 원소를 말한다. 이 때 피벗은 가장 앞에 있는 원소로 선택할 수 있고 구현하는 방법에 따라 random하게 선택할 수도 있다. (여기서는 가장 앞에 있는 원소를 피벗으로 설정할 예정이다.) 다른 모든 원소들을 피벗과 비교하며 피벗보다 ..