분할 정복 방법을 통해 주어진 배열을 정렬한다 💡분할 정복 방법이란? : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 뒤 결과를 모아서 문제를 해결하는 방법
동작 과정
배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
Python 코드
def partition(arr, start, end):
pivot = arr[start]
left = start + 1
right = end
done = False
while not done:
while left <= right and arr[left] <= pivot:
left += 1
while left <= right and pivot <= arr[right]:
right -= 1
if right < left:
done = True
else:
arr[left], arr[right] = arr[right], arr[left]
arr[start], arr[right] = arr[right], arr[start]
return right
def quick_sort(arr, start, end):
if start < end:
pivot = partition(arr, start, end)
quick_sort(arr, start, pivot - 1)
quick_sort(arr, pivot + 1, end)
return arr
Java 코드
//정복
//부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
public void quickSort(int[] array, int left, int right) {
if(left >= right) return;
// 분할
int pivot = partition();
// 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
quickSort(array, left, pivot-1); // 정복(Conquer)
quickSort(array, pivot+1, right); // 정복(Conquer)
}
//분할
//입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들) 로 분할한다.
public int partition(int[] array, int left, int right) {
/**
// 최악의 경우, 개선 방법
int mid = (left + right) / 2;
swap(array, left, mid);
*/
int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
int i = left, j = right;
while(i < j) {
while(pivot < array[j]) {
j--;
}
while(i < j && pivot >= array[i]){
i++;
}
swap(array, i, j);
}
array[left] = array[i];
array[i] = pivot;
return i;
}
개선 방안
partition() 함수에서 피벗 값이 최소, 최대값으로 지정되어 파티션이 나뉘지 않았을 떄, O(n²)의 시간복잡도를 가지게 된다.
정렬하고자 하는 배열이 오름차순이거나 내림차순 정렬이 되어있다면 O(n²)의 시간복잡도를 가진다. 이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도 O(nlog₂n)으로 개선할 수 있다. 하지만, 이 방법으로 개선한다해도 Quick Sort의 최악의 시간복잡도가 O(nlog₂n)가 되는 것은 아니다.
동작 방식(GIF)
시간 복잡도
최선의 경우 : O(nlog₂n)
비교 횟수 : (log₂n)
레코드의 개수가 n²이라 가정, n = 2³(8)일때 2³→ 2² → 2¹순으로 줄어들어 순환 호출의 깊이가 3임
이것을 일반화하면 n = 2ⁿ, n =log₂n이 된다.
각 순환 호출 단계의 비교 연산 : (n)
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
결론, 최선의 시간복잡도는 순환호출의 깊이(log₂n) * 각 순환 호출 단계의 비교 연산(n) = nlog₂n가 된다.
최악의 경우 : O(n²)
비교 횟수 : (n)
레코드의 개수가 n = 2ⁿ일 때, 순환 호출의 깊이는 n이다.
각 순환 호출 단계의 비교 연산 : (n)
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다
결론, 최선의 시간복잡도는 순환호출의 깊이(n) * 각 순환 호출 단계의 비교 연산(n) = n²가 된다.
공간 복잡도
별도의 추가 공간을 사용하지 않고 주어진 배열 안에서만 교환하므로 O(1)이다.
장점
불필요한 데이터의 이동을 줄이고, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성으로 시간복잡도가 다른 정렬 알고리즘에 비해 빠르다.
