수업 중 퀵 정렬에 대해서는 꼭 알고있으면 좋다고 하셔서, 너무 잘 정리해두신 다른 분의 블로그를 보고 정리하며 예전에 배웠던 걸 떠올려봐야겠다.
퀵정렬?
퀵 정렬은 분할 정복 방법으로 주어진 배열을 정렬한다.
* 분할 정복 방법?
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략정렬 과정
- 배열 가운데서 하나의 원소를 고르고, 이 원소를 피벗(pivot) 이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 큰 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.
이렇게 배열을 피벗을 기준으로 둘로 나누는 것을 분할(divide)이라고 한다. 분할을 마친 뒤에 피벗은 더이상 움직이지 않는다. - 분할된 두개의 작은 배열에 대해 재귀적으로 위 과정을 반복한다.
그림으로 보면 쉽게 이해할 수 있다.
출처 : javaguides
위 그림과 같이 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소(pivot)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다고 한다.
위 그림에 맞게 Quick Sort 구현
* 정복 단계
public void quick_sort(int[] array, int left, int right) {
if (left >= right) return;
int pivot = partition();
// pivot을 기준으로 나눈 두 배열을 다시 재귀적으로 탐색(정복)
quick_sort(array, left, pivot-1);
quick_sort(array, pivot+1, right);
}* 분할 단계
public int partition(int[] array, int left, int right) {
int pivot = array[right];
int i = left, j = right;
while (i<j) {
while (array[i] < pivot) {
i++;
}
while (i < j && pivot <= array[j]) {
j--;
}
// j가 i보다 작으면 둘의 자리 바꾸는 함수 따로 작성
swap(array, i, j);
}
array[right] = array[i];
array[i] = pivot;
return i;
}시간 복잡도
만약 이미 주어진 배열이 내림차순, 또는 오름차순으로 정렬되어있어, 배열 분할하는 partition() 함수에서 처음 피벗 값이 최소나 최대값으로 설정되어 파티션이 나누어지지 않았을 때,
최악의 시간 복잡도 O(n^2) 를 가지게 된다.
다만 이런 최악의 경우가 없다면 평균 시간복잡도는 O(nlogn) 이다.
위와 같이 원소의 개수가 n(2^k)개일 때, n -> n/2 -> n/4 -> ... -> 2 -> 1 순으로 부분 배열 크기가 줄어들게 되고, 반면 배열의 개수는 1-> 2 -> ... -> n/4 -> n/2 로 늘어나게 된다. 즉,
n * 1 = n
n/2 * 2 = n
n/4 * 4 = n
...
1 * n = n으로 모든 과정에서 n 번 비교한다.
이 모든 비교가 얼마나 이루어지는지는 다시2*k -> 2*(k-1) -> 2*(k-2) -> ... 2*1 -> 2*0
로 줄어드는 배열 크기를 보면 알 수 있다.
이 비교는 k번 이루어지며, k = log n 이라는 값을 얻을 수 있다.
순환 호출의 깊이(n번의 비교가 얼마나 이루어지느냐)는 log n 이다.
결국 평균 시간복잡도는
몇번의 비교가 이루어지는지 (log n) * 한번의 비교에 소요되는 시간 (n) = O(nlogn)
으로 얻을 수 있다.
글과 그림 참고 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html
