[Algorithm] C++ Quick Sort (퀵정렬)
퀵정렬
- List에서 하나의 피벗을 정하고 이를 기준으로 피벗보다 작은 요소들, 큰 요소들로 두개의 부분 List를 만들어(Divide 분할) 정렬 후 다시 결합(Conquer 정복)을 재귀적으로 반복하는 방법
퀵정렬 알고리즘
1. 리스트 안에 있는 한 요소를 피벗(Pivot)으로 설정한다.
2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값(a)을 찾고, 오른쪽에서부터는 피벗보다 작은 값(b)을 찾는다.
3. a와 b를 교한한다.
4. 왼쪽에서부터 찾은 a값의 위치와 오른쪽에서부터 찾은 b값의 위치가 엇갈리지 않을 때까지 2~3번 과정을 반복한다.
5. 엇갈린 경우에는 오른쪽에서부터 찾은 피벗보다 작은 값(b)과 피벗값을 교환한다.
6. 위의 과정에서 한 번의 분할이 이루어졌고, 두 개의 부분리스트에 대해 다시 1번으로 돌아가 과정을 반복한다.
7. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
예시
피벗(pivot) 값을 선택합니다.
leftmark는 왼쪽 원소로 부터 피벗보다 큰값을 찾고, rightmark는 오른쪽에서 부터 왼쪽으로 이동하며,
피벗보다 작은값을 찾습니다.
이후 leftmark와 rightmark를 교환 해주고, 다시 피벗값을 기준으로 leftmark, rightmark를 찾아줍니다.
이 방법을 반복하다 leftmark가 rightmark보다 오른쪽에 위치할때 멈추게된다.
이 시점에서 rightmark의 위치가 분할지점이 된다.
위의 사진은 피벗인 원소 '54'를 기준으로 왼쪽 원소는 작고 오른쪽 원소는 크다는 특징을 가진다.
이후 새로운 피벗을 정해 위의 작업을 반복하는 재귀적 방법을 사용하여 정렬하면 된다.
아래 이미지는 퀵 정렬 알고리즘을 막대그래프로 쉽게 이해할 수 있도록 나타낸다.
퀵정렬 특징
- 주어진 원소 이외에 다른 추가 메모리를 요구하지 않는 In-place 알고리즘이다.
- 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다.
- 분할 정복 알고리즘을 기반으로 정렬되는 방식으로, 피벗의 값에따라 하나의 리스트에 비균등하게 나뉜다.
- 일반적으로 병합 정렬(Merge Sort) 보다 빠르다.
시간복잡도
- 퀵정렬의 시간복잡도는 O(NlogN)의 시간복잡도를 갖는다.
- Best : O(NlogN)
- Avg : O(NlogN)
- Worst : O(N^2)
관련 알고리즘 문제
https://www.acmicpc.net/problem/3322
3322번: 정렬의 시간복잡도
꿍은 자료구조를 공부할때 각 정렬마다 비교횟수를 구해보라는 문제를 볼때마다 화가난 나머지 세상에서 제일 거지같은 문제를 만들어보고자 다음과 같은 문제를 만들었다. N과 X가 주어질 때,
www.acmicpc.net
Code
#include <iostream>
using namespace std;
void quickSort(int arr[], int start, int end) {
int pivot = start;
int left = pivot + 1;
int right = end;
cout << '\t';
for (int i = 0; i < 9; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
//더 이상 리스트를 분할할 수 없으면 종료
if (start >= end)
return;
//left와 right가 엇갈릴 때까지 반복
while (left <= right) {
for (; left <= end; left++) {
// 피벗 다음 원소부터(왼쪽부터) 큰값 하나씩 찾기
if (arr[left] > arr[pivot])
break;
}
for (; right > pivot; right--) {
// 오른쪽부터 시작해서 피벗보다 작은 값 찾기
if (arr[right] < arr[pivot])
break;
}
// 엇갈리지 않았다면 left값과 right값 교체
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
// 엇갈렸다면 right값과 pivot교체
else {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
}
/*
* 나뉘어진 두개의 분할 리스트 들을 재귀적으로 검색하며 실행
*/
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
int main() {
int arr[9] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };
int arrSize = 9;
cout << "\tresult" << '\n';
quickSort(arr, 0, arrSize - 1);
return 0;
}