알고리즘 개념
- 분할 정복 방법을 통해 큰 문제를 작은 문제 단위로 쪼개면서 해결된다.
- 불안정 정렬에 속한다.
- 보통 프로그래밍 언어에서 sort의 내부적으로 사용된다.
- 임의의 기준 수 pivot을 선택하여 정렬 대상 수들을 pivot 값보다 작은 그룹과 큰 그룹으로 분할한다.
- pivot은 작은 그룹과 큰 그룹 사이로 이동시킨다.
- 분할된 각 그룹에 대해서 재귀적으로 또다시 pivot을 정하고 동일한 과정을 반복한다. 원소가 1개가 되어 더 이상 분할이 불가능할 때까지 반복한다.
알고리즘 배열 내부에서의 분할 과정
- i는 왼쪽 끝, j는 오른 쪽 끝 위치로 둔다.
- pivot을 첫번째 항목으로 선택하고(때에 따라 랜덤이나 중간 값을 선택할 수도 있음) pivot보다 큰 값을 만날 때까지 i값을 1씩 증가시키고, pivot보다 작은 값을 만날 때까지 j값을 1씩 감소시킨다.
- 고정된 i와 j 위치의 수를 교환하고 i<j 일 때까지 이 과정을 반복한다.
- i≥j 이면 분할이 완료된 것으로 list[j]와 pivot을 교환한다.
코드
- pivot을 가장 왼쪽 값으로 설정한 경우
void quicksort(int left, int right){
if(left >= right) return;
int i = left + 1;
int j = right;
int pivot = left;
while(i<=j){
while(i <= right && arr[i] <= arr[pivot]) i++;
while(j > left && arr[j] >= arr[pivot]) j--;
if(i > j){ // 엇갈린 상태
swap(pivot, j);
}
else{
swap(i, j);
}
}
quicksort(left, j-1);
quicksort(j+1, right);
}
2. pivot을 중간 값으로 설정한 경우(최악의 경우를 방지하기 위함)
void swap(int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void quicksort(int left, int right){
if(left >= right) return;
// pivot 중간 index로 지정
int mid = (left + right) / 2;
swap(mid, left);
int pivot = left;
int i = left + 1;
int j = right;
while(i<=j){
while(i <= right && arr[i] <= arr[pivot]) i++;
while(j > left && arr[j] >= arr[pivot]) j--;
if(i > j){ // 엇갈린 상태
swap(pivot, j);
}
else{
swap(i, j);
}
}
quicksort(left, j-1);
quicksort(j+1, right);
}
장점
- 빠르다 O(nlogn)
단점
- 최악의 경우 느리다.
시간 복잡도
- 두 그룹으로 분할하는데 n의 시간이 걸리고 분할된 단계가 long(n) 개 존재하므로 평균 정렬 속도는 O(nlog2 n)
- 분할한 결과가 한쪽으로 몰리는 최악의 경우에는 O(n^2)
공간 복잡도
- O(n)
정렬 알고리즘 시간 복잡도 정리
정렬 | 최선 | 평균 | 최악 |
선택정렬(Selection Sort) | O(n^2) | O(n^2) | O(n^2) |
거품정렬(Bubble Sort) | O(n^2) | O(n^2) | O(n^2) |
삽입정렬(Insertion Sort) | O(n) | O(n^2) | O(n^2) |
퀵정렬(Quick Sort) | O(nlogn) | O(nlogn) | O(n^2) |
병합정렬(Merge Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
힙정렬(Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
728x90
'Algorithm > 개념정리' 카테고리의 다른 글
힙정렬(Heap Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (2) | 2021.01.21 |
---|---|
병합정렬(Merge Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (5) | 2021.01.19 |
삽입정렬(Insertion Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (0) | 2021.01.16 |
거품정렬(Bubble Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (0) | 2021.01.15 |
선택정렬(Selection Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI (0) | 2021.01.14 |