퀵정렬

Question

안녕하세요! 강의 정말 잘 듣고 있습니다! 그런데 퀵정렬 마지막 부분에 조금 이해가 안되는 부분이 있어서 질문드립니다. pivot을 low로 했을때, 잘 정렬된 리스트 일수록 퀵 정렬의 성능이 나빠진다고 하셨는데, 코드를 보면 잘 정렬된 리스트라도 무작위로 정렬된 리스트와 길이가 같다면 단위 연산의 실행횟수는 똑같을것으로 보이는데 왜 성능이 나빠진다고 하는지 궁금합니다. 잘 정렬된 리스트에 수행하지 않아도될 정렬 알고리즘이 수행되어서 비효율적으로 보여서 성능이 나빠졌다고 표현하신건지 궁금합니다!

주니온 · Answer

정렬된 리스트를 가지고 시뮬레이션 해보면 쉽게 이해가 되실 겁니다. S = [ 1, 2, 3, 4, 5] 위의 리스트를 파티션 하면, [1] 과 [2, 3, 4, 5]로 쪼개지지요? S' = [ 2, 3, 4, 5] 도 마찬가지로 [2] , [3, 4, 5]로 쪼개집니다. 이런 식으로 재귀 호출의 깊이가 N이 되므로, Divide-and-Conquer의 장점이 사라지는 것이죠. 동일한 입력으로 Merge Sort를 하면 어떻게 될까요? 재귀 호출을 할 때 마다 N/2으로 쪼개어 지므로, 재귀 호출의 깊이가 logN이 됩니다.