왼쪽 피벗 선택 방식
private static void left_pivotSort(int[] a, int low, int high) {
if( low >= high)
return;
int pivot = partition(a, low, high);
left_pivotSort(a, low, pivot - 1);
left_pivotSort(a, pivot + 1, high);
}
private static int partition(int[] a, int left, int right) {
int low = left;
int high = right;
int pivot = a[left]; //부분리스트의 왼쪽 요소를 피벗으로 설정
while(low < high) {
while(a[high] > pivot && low < high) {
high--; //high의 요소가 pivot보다 작거나 같은 원소를 찾을때까지 high 감소시킴
}
while(a[low] <= pivot && low < high) {
low++; //low의 요소가 pivot보다 큰 원소를 찾을때 까지 low를 증가시킴
}
swap(a, low, high);
}
swap(a, left, low);//pivot으로 설정했던 위치의 원소와 low가 가르키는 원소를 바꾼다.
return low;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
오른쪽 피벗 선택 방식
private static void right_pivotSort(int[] a, int low, int high) {
if( low >= high)
return;
int pivot = partition(a, low, high);
right_pivotSort(a, low, pivot - 1);
right_pivotSort(a, pivot + 1, high);
}
private static int partition(int[] a, int left, int right) {
int low = left;
int high = right;
int pivot = a[right]; //부분리스트의 오른쪽 요소를 피벗으로 설정
while(low < high) {
while(a[low] < pivot && low < high) {
low++; //high가 low보다크면서 low의 요소가 pivot보다 큰 원소를 찾을 때까지 low를 증가시킨다
}
while(a[high] >= pivot && low < high) {
high--; //high가 low보다 크면서, high의 요소가 pivot보다 작거나 같은 원소를 찾을 때까지 high를 감소시킨다
}
swap(a, low, high);
}
swap(a, right, high);//마지막으로 맨처음 pivot으로 설정했던 위치(a[right]) 의 원소와 high가 가리키는 원소를 바꾼다.
return high;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
단점
-가장 이상적으로 분할되었을때 수행시간 : 병합정렬과 같은 모양
T(N) = 2T(N/2) + O(N)
-평균적인 수행시간
T(N) = T(i - 1) + T(N - i) + O(N)
-최악의 시간복잡도: 정렬된 상태의 배열을 정렬할 때
: 분할이 한쪽으로 치중되는 경우
: 각 재귀 레벨에서 N개의 비교작업을 N번 재귀호출 함 = O(N^2)
T(N) = T(N-1) + O(N)
Q. Quicksort의 수행시간이 최악으로 나오는 경우가 어떤 경우인지 서술하고, 이러한 경우를 피할 수 있는 방법에 대해 설명하시오.
-항상 한쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우
T(n) = T(0) + T(n-1) + O(n)
= T(n-1) + O(n)
= T(n-2) + T(n-1) + O(n-1) + O(n)
O(1) + O(2) + ... + O(n-1) + O(n)
=O(n^2)
-이미 정렬된 입력데이터 ( 마지막 원소를 피봇으로 선택하는 경우)
피할 수 있는 방법 : dual-pivot사용하기
임계값을 설정하여 일정 크기 이하로 떨어질 경우 정렬된 배열에서 좋은 성능을 발휘하는 insertion sort(삽입정렬)을 하도록 바꾸면 거의 정렬된 상태에서도 성능 하락을 방지할 수 있다.