QuickSort(퀵 정렬)
October 4, 2019 · View on GitHub
작성자
1. QuickSort란?
- 분할 정복 방법에 근거한 이름 그대로 빠른 정렬이다.
- 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트에 대해 다시 QuickSort를 실행 한다.
- 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되었다. 메모리 참조가 지역화 되어 있기 때문에 CPU 캐시의 hit ratio가 높아진다.1)
QuickSort의 시간 복잡도
- 최악의 경우 : O( n2) (이미 배열이 정렬되어 있거나 역순인 경우)
- 일반적인 경우 : O(nlogn)
2. QuickSort의 구현
- pivot으로 잡을 값 하나를 정한다. (일반적으로 가장 왼쪽이나 오른쪽)
- pivot의 값보다 작은 원소들은 왼쪽에, 큰 원소들은 오른쪽에 재배치한다.
- 이후 나눠진 값에 대해 다시 피벗을 설정한 후 위의 과정을 반복한다.
// 가장 왼쪽값을 피벗으로 잡은 경우
public void quickSort(int[] arr, int left, int right) {
int pivot = arr[left];
int first = left;
int last = right;
while (left < right){
while (pivot <= arr[right] && left < right) right--;
if(left > right) break;
while (pivot >= arr[left] && left < right) left++;
if(left > right) break;
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
int tmp = arr[left];
arr[left] = arr[first];
arr[first] = tmp;
if (first < left) quickSort(arr, first, left - 1);
if (last > right) quickSort(arr, left + 1, last);
}
3. QuickSort의 개선
- 정렬된 배열과 역순 배열일 때 퀵 정렬의 속도가 느려지는 것은 pivot으로 정해진 위치의 값을 택하기 때문에 가장 큰 값이나 가장 작은 값이 pivot이 되기 때문이다.
- 재귀의 깊이가 깊어지고 스택이 넘치며 속도가 느려진다.
- 이를 개선하기 위한 여러 방법이 존재한다.
1) 난수 분할을 사용한 퀵 정렬 개선
- pivot을 선택하는 대안으로 pivot을 난수로 선택하는 것이다. 확률적으로 퀵 정렬의 속도 향상을 기대 할 수 있다.
- 0부터 n-1 범위의 난수를 발생시켜 난수의 위치와 배열의 제일 오른쪽 요소의 위치를 바꾼 후에 퀵 정렬 알고리즘을 수행한다.
- 평균적으로 고른 속도 향상은 있을 수도 있지만 속도의 결과가 확률에 맡겨지게 된다.
2) 삽입 정렬을 사용한 퀵 정렬 개선
- 삽입 정렬은 구현이 간단하고 크기가 작은 배열에서는 매우 효율이 좋다.
- 삽입 정렬은 추가적인 메모리를 필요로 하지 않는다.
- 작은 구간에 대해서는 삽입 정렬을 사용하면서 퀵 정렬의 재귀의 깊이를 줄여줌으로써 속도의 향상을 기대할 수 있다.
- 구간의 크기가 너무 큰 경우 삽입 정렬은 큰 크기의 배열에서 성능이 좋지 못하여 전체적인 성능이 떨어진다.
- 퀵 정렬 종료 조건을 분할 리스트의 크기가 적절한 크기(100~200)보다 작을 때로 변경하고, 작을 때는 삽입정렬을 수행하도록 변경한다.
3) 세 값의 중위 값을 구한 퀵 정렬의 개선2)
- 배열의 가장 왼쪽 값
a[left], 가장 오른쪽 값a[right], 중간의 값a[(left+right)/2]3개의 값을 사용한다. 이 세 값을 오름차순으로 정렬한다. - 중간 값
a[(left+right)/2]을 가장 오른쪽의 앞의 값a[right-1]과 위치를 바꾼다. - 배열의 첫 번째 값은 마지막의 앞의 값보다 항상 작고, 마지막 값은 마지막 앞의 값보다 항상 크다.
a[left] < a[right-1] < a[right] - 분할 구간은 배열 앞에서 두 번째 값과 뒤에서 세 번째 값으로 좁혀진다.
a[left+1]부터a[right-2]까지 - 정렬 범위에서 2개를 줄이므로 재귀의 깊이를 줄일 수 있으며 분할도 대부분 중앙에서 이루어진다.
- 최악의 경우인 정렬된 배열이나 역순의 배열의 경우 분할을 중앙에서 할 수 있으므로 이 방법을 쓰면 속도가 빨라진다.