[Algorithm] Quick Sort(퀵 정렬)
1. 정의
- 피벗(기준)을 하나를 정해서 피벗보다 큰 수는 오른쪽 작은수는 왼쪽으로 옮겨가며 정렬하는 기법
- 불안정 정렬
- 시간 복잡도
- 평균 : $O(nlogn)$
- 최악 : $O(n^2)$
2. 동작 과정
- 피벗을 하나 정한다.
- 양 끝에 포인터를 각각 두고 포인터를 움직인다.
2 - 1. 왼쪽 포인터는 피벗 보다 큰 값이 나올때까지 오른쪽으로 움직인다.
2 - 2. 오른쪽 포인터는 피벗 보다 작은 값이 나올때까지 왼쪽으로 움직인다.
2 - 3. 값을 찾으면 서로 교환한다.
2 - 4. (2 - 1) ~ (2 - 3)을 반복한다.
- 포인터가 서로 교차하면 2개의 구간이 생기는데, 각각의 구간 별로 1번부터 반복한다.
3. 장단점
- 장점
- 병합 정렬과는 달리 추가적인 공간이 필요하지 않음
- 단점
- 피벗에 따라 속도가 달라질 수 있음
- 피벗을 임의로 잡기 때문에 LinkedList에서는 효율이 나쁨
4. 코드
public void quickSort(int[] array, int left, int right) {
int part2Start = partition(arry, left, right);
int part1End = part2Start - 1;
if (left < part1End) {
quickSort(array, left, part1End);
}
if (part2Start < right) {
quickSort(array, part2Start, right);
}
}
//두 개의 구간중 오른쪽 구간의 첫번째 인덱스를 반환한다.
public static int partition(int[] array, int left, int right) {
int pivot = array[(left + right) / 2];//피벗은 중간지점으로 정함
while (left <= right) {
while (array[left] < pivot) { //왼쪽에서 피벗보다 큰 값 찾기
left++;
}
while (array[right] > pivot) { //오른쪽에서 피벗보다 작은 값 찾기
right--;
}
if (left <= right) {
swap(array, left++, right-- );
}
}
return left;
}
private static void swap(int[] array, int left, int right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
※ 참고
