- quick sort
- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현
- 합병 정렬과 달리 비균등하게 분할
- 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택하고 피벗을 기준으로 분할
- 속도가 빠르고 추가 메모리 공간을 필요로 하지 않음, 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인
- 시간 복잡도 분석
: 재귀 호출의 깊이는
: 각각의 패스에서 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어짐, 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시
: 총 시간 복잡도는
- 단점으로
: 정렬된 리스트에 대해서는 오히려 수행시간이 되버리는 불균형 분할 발생 -> 단순히 왼쪽 데이터를 피벗으로 사용하지 않고 리스트 내의 몇개의 데이터 중에서 크기순으로 중간 값(median)을 피벗으로 선택하여 극복 (왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간값을 선택하는 방법(median of three)
- CODE
#include < iostream> using namespace std; int arr[1000001]; int partition(int *a, int low, int high) { int pivotIndex = low + (high - low) / 2; int pivotValue = arr[pivotIndex]; swap(arr[pivotIndex], arr[high]); int pos = low; for (int i = low; i < high; i++) { if (a[i] < pivotValue) { swap(a[i], a[pos]); pos++; } } swap(arr[pos], arr[high]); return pos; } void quicksort(int *a, int low, int high){ if (low < high) { int pivot = partition(a, low, high); quicksort(a, low, pivot - 1); quicksort(a, pivot + 1, high); } } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } quicksort(arr, 0, n - 1); for (int i = 0; i < n; i++) { cout << arr[i] << "\n"; } return 0; }
'Algorithm' 카테고리의 다른 글
알고리즘 - 기수 정렬 (0) | 2015.11.12 |
---|---|
알고리즘 - 힙 정렬 (0) | 2015.11.12 |
알고리즘 - 합병 정렬 (0) | 2015.11.12 |
알고리즘 - 셸 정렬 (0) | 2015.11.12 |
알고리즘 - 버블 정렬 (0) | 2015.11.12 |