* 피벗(pivot)은 항상 정렬할 배열 가장 왼쪽을 기준으로 한다.
#include <iostream>
using namespace std;
void QuickSort(int A[], int n);
int Partition(int A[], int n);
int main()
{
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << "초기 배열: " ;
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << "\n";
QuickSort(arr, n);
cout << "최종 배열: " ;
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << "\n";
return 0;
}
void QuickSort(int A[], int n) {
if (n > 1) {
int pivot = Partition(A, n);
int* left = new int(pivot);
for (int i = 0; i < pivot; i++) {
left[i] = A[i];
}
QuickSort(left, pivot);
for (int i = 0; i < pivot; i++) {
A[i] = left[i];
}
int* right = new int(n-pivot);
for (int i = 0; i < n-pivot-1; i++) {
right[i] = A[pivot+i+1];
}
QuickSort(right, n-pivot-1);
for (int i = 0; i < n-pivot-1; i++) {
A[pivot+i+1] = right[i];
}
}
}
int Partition(int A[], int n) {
int Left = 1, Right = n-1;
while(Left <= Right) {
while(Left < n && A[Left] < A[0]) Left++;
while(Right > 0 && A[Right] >= A[0]) Right--;
if(Left < Right){
int temp = A[Left];
A[Left] = A[Right];
A[Right] = temp;
} else {
int temp = A[0];
A[0] = A[Right];
A[Right] = temp;
}
}
return(Right);
}
input
10 50 23 84 49 71 15 99 62 36 7
result
초기 배열: 50 23 84 49 71 15 99 62 36 7
최종 배열: 7 15 23 36 49 50 62 71 84 99
