Quick Sort
분할 정복 (divdie and conquer) 방법을 통해 주어진 배열을 정렬한다.
분할 정복 : 문제를 작은 문제로 분할해서 해결한 다음, 합쳐서 결과를 내는 방법.
피벗을 선택해서 피벗을 기준으로 배열을 분할해서 정렬한다.
피벗으로 배열이 불균형하게 분할될수록 성능이 저하된다.
그래서,
피벗의 선택 방법이 중요하다.
그래서 이미 정렬된 배열에 대해 퀵 정렬을 실행하면 최악의 시간복잡도를 가진다.
피벗을 배열의 중간값으로 설정해서 최적화 할 수 있다.
시간 복잡도 : 최선의 경우 O(nlog2N), 최악의 경우 O(N^2), 평균 O(nlog2N)
정렬 과정
-
배열에서 하나의 원소
피벗을 고른다. -
피벗보다 큰값은 피벗의 오른쪽으로 피벗보다 작은 값은 피벗의 왼쪽으로 옮긴다. 이 과정을
파티셔닝이라고 한다. -
선택한 피벗에 대해서 파티셔닝이 끝나게 되면 i(왼쪽 인덱스) == j(오른쪽 인덱스) == 선택한
피벗의 최종 위치가 된다. -
재귀적으로 반복한다.
void quickSort( int[] array, int left, int right)
{
if (left == right) return;
// 이번 배열의 원소의 갯수가 1 즉, 정렬이 완료된것
int mid = (left + right) / 2;
int pivot = array[mid];
int i = left, j = right;
// 파티셔닝
while (i != j)
{
// 오른쪽과 왼쪽이 교차되면 종료한다.
while (pivot < array[j])
{
j--;
// array[j]의 값이 pivot 보다 크다면 j--
}
// pivot보다 작거나 같은 값을 찾는다면 멈추게 된다.
while (i != j && pivot >= array[i])
{
i++;
// array[i]의 값이 pivot 보다 작거나 같다면 i++
}
// 1. i == j 라면 멈추게된다.
// 2. pivot보다 큰 값을 찾으면 멈추게된다.
// 피벗의 왼쪽에 있는 큰값과
// 피벗의 오른쪽에 있는 작은값을 교환
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
// while 문은 i == j == pivot의 자리의 상태로 멈추게된다.
array[mid] = array[i];
array[i] = pivot;
mid = i;
// pivot의 자리는 확정이므로 피벗의 왼쪽과 오른쪽 배열에 대해서 똑같이 정렬한다.
quickSort(array, left, mid - 1);
quickSort(array, right, mid + 1);
}