퀵 정렬의 메커니즘은 크게 다음과 같다.
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.
이 부분에서 만약 알고리즘에 대해 잘 알고있다면 '분할 정복(Divide and Conquer)'을 떠올릴 것이다.
병합정렬과의 차이점
병합정렬: 하나의 리스트 절반으로 나누어 분할 정복
퀵 정렬: 피벗의 따라 나누기 때문에 부분리스트 크기가 다를 수도 있음
퀵 정렬 특징
비교 정렬 : 구체적으로 알아보기에 앞서 미리 언급하자면 퀵 정렬은 데이터를 '비교한다.
제자리 정렬(in-place sort) : 추가적인 공간을 필요로 하지 않는다.
불안정정렬(Unstable Sort): 퀵 정렬은 병합정렬과는 다르게 하나의 피벗을 두고 두 개의 부분리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정정렬 알고리즘이기도 하다.
왼쪽 피벗 선택 방식
퀵 정렬 코드
public class QuickSort {
public static void sort(int[] a) {
l_pivot_sort(a, 0, a.length - 1);
}
/**
* 왼쪽 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void l_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
int pivot = partition(a, lo, hi);
l_pivot_sort(a, lo, pivot - 1);
l_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(lo)를 반환
*/
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[left]; // 부분리스트의 왼쪽 요소를 피벗으로 설정
// lo가 hi보다 작을 때 까지만 반복한다.
while(lo < hi) {
/*
* hi가 lo보다 크면서, hi의 요소가 pivot보다 작거나 같은 원소를
* 찾을 떄 까지 hi를 감소시킨다.
*/
while(a[hi] > pivot && lo < hi) {
hi--;
}
/*
* hi가 lo보다 크면서, lo의 요소가 pivot보다 큰 원소를
* 찾을 떄 까지 lo를 증가시킨다.
*/
while(a[lo] <= pivot && lo < hi) {
lo++;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[left])의 원소와
* lo가 가리키는 원소를 바꾼다.
*/
swap(a, left, lo);
// 두 요소가 교환되었다면 피벗이었던 요소는 lo에 위치하므로 lo를 반환한다.
return lo;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}