Quicksort from CTCI

코딩 인터뷰 완전 분석(원제: Cracking the Coding Interview)에 소개된 Quicksort를 다시 한 번 정리 해보려고 한다.

기본적으로 퀵정렬은, 무작위로 한 원소를 정하고(이를 pivot이라 부른다), pivot보다 작은 원소들은 앞쪽에, 큰 원소들은 뒷쪽에 위치시킨다. 

• 실행시간: 평균 O(n logn), 최악 O(n^2).
• 메모리: O(logn)

배열 분할(partition)에 사용되는 원소(pivot)가 배열의 중간값(median) 혹은 중간값에 가까운 값이라면 좋은 성능이 나오겠지만, 반드시 그러리라는 보장은 할 수 없다. 즉 퀵정렬은 pivot을 어떻게 정하느냐에 따라 느리게 동작할 수도 있으며, 최악의 경우 수행시간이 O(n^2)이 될 수 있다.

이전에 작성했던 퀵정렬(Hoare's Scheme)과 다른 점은, pivot을 배열의 첫번째 원소가 아니라 중간에 위치한 원소로 정한다는 것이다. 왼쪽에서는 pivot보다 큰 원소, 즉 왼쪽에서 오른쪽으로 옮겨줘야 하는 원소를 찾고, 오른쪽에서는 pivot보다 작은 원소, 즉 오른쪽에서 왼쪽으로 옮겨줘야 하는 원소를 찾은 뒤 swap하는 방식이다.