재귀 호출이 한 번 진행 될 때 마다 최소한 하나의 원소는 최종적으로 위치가 정해져있음으로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
private static void quickSort(int[] arr, int left, int right)}
int L = left;
int R = right;
int pivot = arr[(left+right)/2]; //가운데 요소 피벗 지정
while(L <= R){
//피벗 왼쪽에는 피벗보다 작은 원소들이 위치해야 하고, 큰 원소강 있다면 반복문을 나온다.
while(arr[L]<pivot) L++;
//피벗 오른쪽에는 피벗보다 큰 원소들이 위치해야 하고, 작은 원소가 있따면 반복문을 나온다.
while(arr[R]>pivot) R--;
//L과 R이 역전되지 않고, 같은 경우가 아니라면 두 원소는 위치를 교환한다.
//이를 통해 피벗 기준으로 왼쪽에는 작은 원소가, 오른쪽에는 큰 원소가 위치하게 된다.
if(L <= R){
if(L != R){
swap(arr, L, R);
}
L++;
R--;
}
}
//L과 R이 역전된 후에 피벗의 왼쪽과 오른쪽에는 정렬되지 않은 부분 배열이 남아있을 수 있따.
// 이 경우, 남아있는 부분 배엘애 대해 퀵 정렬을 수행한다.
if(left<R) quickSort(arr,left, R);
if(L<right) quickSort(arr,L,R);
}
private static void swap(int[] arr, int left, int right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
하지만, 이 방법으로 개선하더라도 퀵 정렬의 최악의 시간 복잡도가 O(NlogN)이 되는 것은 아니다.
즉, N=2^k의 경우, k=logN이다.
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 N번 정도 비교가 이루어진다.
따라서, 최선의 시간 복잡도는 순환 호출의 깊이(logN) x 각 순환 호출 단계의 비교 연산(n) = nlogn
이 된다.
이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.
최악의 경우 : T(N) = O(N^2)
최악의 경우는 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있는 경우이다.
비교 횟수 : (N)
레코드의 개수 N이 2의 거듭제곱이라고 가정할 때, 순환 호출의 깊이는 N이다.
순환 호출의 깊이 x 각 순환 호출 단계의 비교 연산 = N^2
이다.Quick Sort는 평균적으로 가장 빠른 정렬 알고리즘이다.
Arrays.sort()를 할때 내부적으로 Dual Pivot Quick Sort라고 ..