Quick_Sort.cpp

#include<iostream>

using namespace std;

int a[108000];

int partition(int l, int r){
	int tmp;//入れ替え用の変数
	while(1){
		//1. rを左に動かす
		while(a[l] <= a[r]){
			r--;
			if(l == r){
				return r;
			}
		}
		//2. 入れ替え
		tmp = a[l];
		a[l] = a[r];
		a[r] = tmp;
		//3. lを右に動かす
		while(a[l] <= a[r]){
			l++;
			if(l == r){
				return r;
			}
		}
		//4. 入れ替え
		tmp = a[l];
		a[l] = a[r];
		a[r] = tmp;
	}
}

void quick_sort(int l, int r){
	if(r <= l){
		return;
	}
	int p = partition(l, r);
	quick_sort(l, p-1);
	quick_sort(p+1, r);
}

int main(){
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	quick_sort(0, n-1);
	
	for(int i = 0;i < n;i++){
		cout << a[i] << " ";
	}
	cout << endl;
}