코딩하는 털보

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 퀵 정렬은 병합 정렬과 동일하게 분할 정복을 사용하여 정렬 문제를 해결한다. 퀵 정렬의 특별한 점은 pivot이라는 개념을 사용하는데, 배열 요소 중 하나를 pivot으로 정하여 pivot보다 작은 값을 왼쪽으로 큰 값을 오른쪽으로 배치하고 분할된 두 영역에 다시 위 과정을 크기가 1이 될 때 까지 반복하여 마지막에 모두 합치면 정렬되는 방식이다. 퀵 정렬의 시간복잡도는 O(nlogn)이다. Big O notation은 알다시피 가장 최악의 상황에서의 시간복잡도를 표현하는데, 퀵정렬의 최악의 시나리오에서 시간복잡도는 O(n^2)이다. 하지만 퀵 정렬은 특별하게 pivot을 어떤 요소로 선택하느냐에 따..