[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)이란?

제자리 정렬(in-place sorting) 알고리즘의 하나이다.
👉퀵 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다.

퀵 정렬(Quick Sort)의 방법

✏하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.

피벗(pivot)을 선택하는 과정에 있어서,

• 왼쪽 피벗 선택 방식
• 중간 피벗 선택 방식
• 오른쪽 피벗 선택 방식

으로 총 세가지 방법이 있다(결과는 동일).

❗ 만약 바로 정렬 된 상태의 배열을 정렬하고자 할 때,
왼쪽 또는 오른쪽 피벗이 가장 작거나 큰 요소가 되므로, 부분리스트는 N-1개의 요소를 갖게 되고, 분할은 N번 만큼 진행될 것이다.
이러한 경우 시간 복잡도는 O(N^2), 공간 복잡도는 O(N)으로 최악의 성능을 내게 된다.

👉 그러므로 중간지점에 가까운 위치에서 왼쪽 오른쪽 리스트가 균형에 가까운 트리를 얻어낼 수 있는 중간 피벗 선택 방식을 지향한다.

퀵 정렬(Quick Sort)의 장단점

👍 평균 시간 복잡도는 NlogN이고, 다른 NlogN 알고리즘에 비해 대체적으로 속도가 매우 빠르다.

👎 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.
👎 정렬된 상태의 배열을 정렬할 때엔 성능이 급격하게 낮아진다.

Reference

• Stranger's LAB
• heejeong Kwon