이미 정렬된 배열
피벗 선택이 첫 번째 또는 마지막 원소: 이 경우, 분할이 매우 불균형적으로 일어나므로 시간복잡도는 O(n^2)이 됩니다
중복된 값이 많은 배열
어떤 피벗 선택 기준을 사용하더라도: 중복된 값이 많을 경우, 피벗을 어떻게 선택하더라도 분할이 불균형적으로 일어날 가능성이 높습니다. 이로 인해 시간복잡도가
O(n^2)에 가까워질 수 있습니다.
이러한 문제를 해결하기 위한 몇 가지 방법은 다음과 같습니다\
-
3-분할 퀵소트 (3-way Quick Sort): 중복된 값이 많을 때 효율적입니다. 피벗과 같은 원소들을 별도로 처리하여 분할을 더 균형적으로 만듭니다.
-
랜덤 피벗 선택: 이미 정렬된 배열에 대해서는 랜덤 피벗 선택이 유용할 수 있습니다. 하지만 중복된 값이 많은 경우에는 큰 효과를 보이지 않을 수 있습니다.
-
하이브리드 정렬: 퀵소트와 다른 정렬 알고리즘 (예: 삽입 정렬)을 조합하여 사용합니다. 작은 서브배열에 대해서는 삽입 정렬을 사용하는 것이 효율적일 수 있습니다.
-
피벗 선택의 다양화: 중앙값을 피벗으로 선택하거나, 여러 후보 중에서 피벗을 선택하는 등의 방법을 사용할 수 있습니다.
3-분할 퀵소트(3-way Quick Sort)는 피벗을 하나만 사용하지만, 배열을 피벗과 비교하여 세 부분으로 나눕니다. 이 세 부분은 다음과 같습니다:
피벗보다 작은 원소들: 이 부분은 피벗의 왼쪽에 위치합니다.
피벗과 같은 원소들: 이 부분은 피벗의 위치에 있습니다.
피벗보다 큰 원소들: 이 부분은 피벗의 오른쪽에 위치합니다.
이렇게 하면 중복된 원소가 많은 경우에도 효율적으로 정렬할 수 있습니다. 피벗과 같은 원소들은 이미 정렬된 상태이므로 다음 재귀 호출에서는 그 부분을 제외할 수 있습니다. 따라서 3-분할 퀵소트는 중복된 원소가 많은 배열에서 효율적으로 작동합니다.
기존의 퀵소트와는 달리, 3-분할 퀵소트는 피벗과 같은 원소들을 별도로 처리하기 때문에, 중복된 값이 많아도 불균형한 분할을 피할 수 있습니다. 이로 인해 성능이 개선됩니다.
