[Algorithm] Quick Sort

 

소스코드

#include <cstdio>
#include <algorithm>

using namespace std;
 
const int MX = 50001;
 
int partition(int* a, int left, int right)
{
    int pivot_idx = (left + right) / 2;
    int pivot_val = a[pivot_idx];
     
    swap(a[right], a[pivot_idx]);
 
    int cnt = left;
    for (int i = left; i < right; ++i) {
        if (a[i] <= pivot_val) {
            swap(a[i], a[cnt++]);
        }
    }
    swap(a[right], a[cnt]);
    return cnt;
}

void qsort(int* a, int l, int r)
{
    if (l <= r) {
        int pivot = partition(a, l, r);
        qsort(a, pivot + 1, r);
        qsort(a, l, pivot - 1);
    }
}

int main()
{
    int n, a[MX];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    
    qsort(a, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        printf("%d\n", a[i]);
    }
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.