[알고리즘] 정렬 - 퀵 정렬, O(NlogN)
평균적인 상황에서 높은 성능을 발휘하는 퀵 정렬이다. C++ STL 자료구조의 정렬에서 사용되는 것으로 알고 있다. 퀵 정렬은 최악의 상황 (후술)에서는 O(N^2)까지 시간 복잡도가 증가할 수도 있지만 대부분의 상황에서는 O(NlogN) 안에서 해결된다. O(NlogN)이라는 것은 MergeSort와 비슷한 구조의 알고리즘이라는 것이고, 실제로 동작 방식에 차이는 있지만 더 작은 문제로 쪼개서 해결한다는 점은 동일하다. MergeSort와의 큰 차이점에는 1. 문제가 쪼개지는 균형이 보장되지 않는다, 2. MergeSort는 작은 문제를 해결한 뒤 합치는 방식 (bottom-up)이라면 QuickSort는 큰 문제부터 해결하면서 정렬되는 방식 (top-down)이다. 가 있다. 퀵 정렬 (Quick S..
알고리즘
2024. 3. 17. 08:08
