ki hyun's 개발블로그

🚨 이번 포스트는 복잡한 식과 머리 아픈 내용이 나올 수 있습니다. 퀵 정렬의 성능 저번 포스트에서는 퀵 정렬에 대해 알아보았다. 퀵 정렬의 평균적인 수행시간이 O(n log n) 이고 최악의 수행시간이 O(n^2) 이라는 것을 알았지만 최악의 수행시간이 O(n^2) 이나 되는 알고리즘이 어째서 힙 정렬보다 더 빠른지에 대해서는 자세히 다루지 않았다. 이번 포스트에서는 퀵 정렬의 성능에 대해 알아보고 어째서 퀵 정렬이 힙 정렬보다 더 효율적인 알고리즘인가에 대해 알아볼 것이다. 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한가 아닌가에 따라 달라진다. 분할이 균등하게 된다면 퀵 정렬은 병합 정렬처럼 빠르게 작동한다. 하지만 분할의 균등하지 않다면 삽입 정렬처럼 느리게 동작한다. 분할을 가장 나쁘..