이번 글은 정렬 알고리즘 중에서 Quick Sort에 대한 글입니다. 퀵 정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속합니다. 퀵 정렬은 합병정렬과 비슷하게 분할 정복(Divide And Conquer)알고리즘을 사용합니다. C++ STL의 sort()의 경우 순차열 [b, e) 원소들을 퀵 정렬로 수행하기 때문에 평균적으로는 O(N log N)의 시간복잡도를 보장을 하며 최악의 경우 O(N^2)의 시간 복잡도를 가집니다. 퀵 정렬의 원리는 pivot을 임의의 인덱스에 하나잡은 뒤 Left/Right Pivot을 양 끝으로 잡고 현재 Pivot보다 작은 값들은 왼쪽으로, Pivot보다 큰 값들은 오른쪽으로 옮기면 됩니다! 이후 Pivot을 제외한 왼쪽 부분과 오른쪽 ..