//
// Created by Martin on 2022/4/8.
//

#ifdef __GUNC__
#include <bits/stdc++.h>

#else
#include <vector>
#include <iostream>
#include <random>

#endif // __GUNC__


using namespace std;

//------------------------------------------------
// 快速排序

class QuickSort {
public:
	// 对A[p..r]进行排序, 小->大
	static void quickSort(vector<int>& A, int p, int r) {
		if (p < r) {
			// 对A[p, r]进行一次划分, 找枢轴位置q
			int q = partition(A, p, r);

			if (p < q)
				quickSort(A, p, q - 1);
			if (q < r)
				quickSort(A, q + 1, r);
		}
	}

	// 对A[p..r]进行一次划分, 枢轴位置q.
	// 满足A[p..q-1] <= A[q] <= A[q+1..r]
	static int partition(vector<int>& A, int p, int r) {
		int x = A[r];
		int i = p - 1;
		for (int j = p; j < r; ++j) {
			if (A[j] <= x) {
				++i;
				std::swap(A[i], A[j]);
			}
		}

		std::swap(A[i + 1], A[r]);
		return i + 1;
	}

	static int partition_2(vector<int>& A, int p, int r) {
		int pivot = A[p];
		int low = p, high = r;
		while (low < high) {
			while (low < high && A[high] >= pivot) { --high; }
			A[low] = A[high];
			while (low < high && A[low] <= pivot) { ++low; }
			A[high] = A[low];
		}
		A[low] = pivot;
		return low;
	}
};

//------------------------------------------------
// 测试

void print_vector(vector<int>& vec) {
	cout << "{";
	for (int i = 0; i < vec.size(); ++i) {
		cout << vec[i];
		if (i < vec.size() - 1) {
			cout << ", ";
		}
	}
	cout << "}" << endl;
}

int main()
{
	// 生成 TestCase
	default_random_engine e;
	uniform_int_distribution<int> u(1, 100);
	const int kTestNum = 50;
	vector<int> vec;
	for (int i = 0; i < kTestNum; ++i) {
		vec.push_back(u(e));
	}

	// 打印 TestCase
	cout << "origin vector=";
	print_vector(vec);

	// 堆排序
	QuickSort::quickSort(vec, 0, vec.size() - 1);
	cout << "after quicksort, vector=";
	print_vector(vec);

	return 0;
}