퀵정렬은 불안정 정렬(같은 값에서도 기존의 순서가 바뀔 수 있는 정렬 방식)이며 평균적으로 매우 빠른 수행 속도를 냅니다.
또한 합병정렬과 같이 분할정복 알고리즘 중 하나이지만, 합병정렬과의 차이점은 퀵 정렬은 리스트를 비균등하게 분할한다는 것입니다.
퀵 정렬은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고,
해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고
다시 왼쪽 파티션 구간에 한하여 pivot을 잡고 파티션을 나누고 오른쪽 파티션 구간에서도 pivot을 잡고
파티션을 나누는 과정을 반복하여 정렬시키는 정렬 알고리즘입니다.
이 알고리즘의 핵심은 pivot을 잘 설정하여 왼쪽 파티션과 오른쪽 파티션을 적절하게 나누는 것입니다.
왜냐하면 pivot을 해당 구간의 중앙값으로 잘 설정하면 merge sort와 같은 시간 복잡도 O(nlogn)에 수행할 수 있지만,
만약 매 케이스마다 구간의 가장 큰 값이나 가장 작은 값으로 나눠버리면 O(n^2)의 수행 시간을 갖게 됩니다. (평균적으로는 O(nlogn))
피벗을 제일 왼쪽으로 정한 퀵소트 코드
입력
첫 줄에 정렬할 원소의 수 N
둘째 줄부터 정렬할 원소 N개의 정수가 주어집니다.
Sample Input
6
15 4 7 3 6 1
출력
퀵 정렬 후 정렬된 원소 결과를 출력합니다.
Sample Output
1 3 4 6 7 15
#include <stdio.h>
int N;
int arr[1000];
void quickSort(int *arr, int left, int right) {
int pivot, left_temp, right_temp;
left_temp = left;
right_temp = right;
pivot = arr[left];//피벗을 왼쪽 처음부터 시작한다고 가정
while (left < right) {//left가 right를 넘을때까지
while (arr[right] >= pivot && (left < right))
right--;
if (left != right)
arr[left] = arr[right];
while (arr[left] <= pivot && (left < right))
left++;
if (left != right)
arr[right] = arr[left];
}
arr[left] = pivot;
pivot = left;
if (left_temp < pivot) quickSort(arr, left_temp, pivot - 1);
if (right_temp > pivot)quickSort(arr, pivot + 1, right_temp);
}
int main() {
scanf_s("%d", &N);
for (int i = 0; i < N; i++)
scanf_s("%d", &arr[i]);
quickSort(arr, 0, N - 1);
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
}