퀵 정렬 함수

#include <iostream>
#include <cstring>
using namespace std;

template<typename T, size_t s>
inline size_t arsize(T (&a)[s]){return s;}

void quick_sort(int* arr, int left, int right) {
	
    //단순 삽입 정렬 이용해 처음, 가운데, 끝 요소를 오름차순 정렬함
    int tmp[3]={left, (left+right)/2, right};
    for(int i=1;i<3;i++){
    	int t=arr[tmp[i]], j=i;
    	for(; j>0 && arr[tmp[j-1]]>t; j--)
    		arr[tmp[j]]=arr[tmp[j-1]];
    	arr[tmp[j]]=t;
    }
    //가운데 요소와 끝에서 2번째 요소 교환
    swap(arr[tmp[1]], arr[right-1]);
    //이후 정렬 범위는 축소되고 끝에서 2번째 값을 피벗으로 설정
    int pl=left+1, pr=right-2, pivot=arr[right-1];
    //이유는 위에서 수행한 세요소의 정렬때문에 a[left]는 피벗 이하
    //a[right-1], a[right]는 피벗 이상의 값인게 확정됨
    
    while (pl<= pr) {
        while (arr[pl] < pivot)
            pl++;
        while (arr[pr] > pivot)
            pr--;
        if (pl<= pr)
        {
            swap(arr[pl], arr[pr]);
            pl++;
            pr--;
        }
    }

    if (left < pr)
        quick_sort(arr, left, pr);

    if (pl < right)
        quick_sort(arr, pl, right);
}

int main() {
	// your code goes here
	int a[]={1,5,85,8,0,-10,32};
	cout<<"정렬 전\n";
	for(int i=0;i<arsize(a);i++)
		cout<<a[i]<<' ';
	cout<<'\n';
	
	quick_sort(a, 0, arsize(a)-1);
	
	cout<<"정렬 후\n";
	for(int i=0;i<arsize(a);i++)
		cout<<a[i]<<' ';
	cout<<'\n';	
	return 0;
}