Hya 개발스토리

* 피벗(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