개념
하나의 리스트를 피벗을 기준으로 분할하고 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하는 과정을 반복한 다음,
정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬
합병 정렬(Merge Sort)와 달리 퀵 정렬은 리스트를 비균등하게 분할
속도가 빠름
정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 수행시간이 오래 걸림
1. 리스트 가운데서 하나의 원소를 고른다. (이렇게 고른 원소 = 피벗)
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록
피벗을 기준으로 리스트를 둘로 나눈다. (이렇게 리스트를 둘로 나누는 것 = 분할)
분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다.
(재귀는 리스트의 크기가 0이나 1이 될 때까지 반복)
시간 복잡도
Worst Case - O(n^2)
Best Case - O(n log n)
Average Case - O(n log n)
Worst Case => 이미 정렬된 경우, 피벗을 가장 크거나 작은 값들만 고르는 경우
예제 코드
void quickSort(int i, int j)
{
if (i >= j)
{
return;
}
int pivot = array[(i + j) / 2];
int left = i;
int right = j;
while (left <= right)
{
while (array[left] < pivot)
{
++left;
}
while (array[right] > pivot)
{
--right;
}
if (left <= right)
{
swap(array[left], array[right]);
++left;
--right;
}
}
quickSort(i, right);
quickSort(left, j);
}
'자료구조' 카테고리의 다른 글
[자료구조] Heap Sort (힙 정렬) (0) | 2021.02.12 |
---|---|
[자료구조] Merge Sort (합병 정렬) (0) | 2021.02.11 |
[자료구조] Select Sort (선택 정렬) (0) | 2021.02.10 |
[자료구조] Insert Sort (삽입 정렬) (0) | 2021.02.08 |
[자료구조] Bubble Sort (버블 정렬) (0) | 2021.02.06 |