퀵 정렬
#include <iostream>
using namespace std;
int n, cnt;
int arr[] = { 4, 2, 6, 1, 5, 3 };
void quickSort(int s, int e) {
if (s >= e) //원소가 1개인 경우
return;
int pivot = s; //피벗은 첫번째 원소
int left = s+1, right = e;
int temp;
while (left <= right) { //엇갈릴 때까지 반복
while (arr[left] <= arr[pivot]) //피벗보다 큰 값을 만날 때까지 이동
left++;
while (arr[right] >= arr[pivot] && right > s) //피벗보다 작은 값을 만날 때까지 이동
right--;
if (left > right) {
temp = arr[right];
arr[right] = arr[pivot];
arr[pivot] = temp;
}
else {
temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
}
quickSort(s, right - 1);
quickSort(right + 1, e);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
quickSort(0, 5);
for (int i = 0; i < 6; i++)
cout << arr[i] << ' ';
return 0;
}
시간 복잡도
평균- O(NlongN)
최악- O(N^2)
'알고리즘 > C++' 카테고리의 다른 글
[알고리즘] 탐욕(그리디) 알고리즘 (0) | 2021.11.01 |
---|---|
[알고리즘] 병합 정렬 - C++ (0) | 2021.09.22 |
[알고리즘] 삽입 정렬 - C++ (0) | 2021.09.22 |
[알고리즘] 선택 정렬 - C++ (0) | 2021.09.22 |
[알고리즘] 버블 정렬 - C++ (0) | 2021.09.22 |
댓글