// Tri rapide (Quick Sort)
// https://www.geeksforgeeks.org/quick-sort-algorithm/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Fonction pour partitionner le tableau
int partition(vector<int> &arr, int low, int high)
{
	int pivot = arr[high];	// Choisir le pivot (dernier élément)
	int i = low - 1;	// Indice pour les éléments plus petits que le pivot

	// On parcourt arr[low .. high] et on déplace tous les éléments <= pivot à gauche.
	// Après chaque itération, tous les élément de arr[low ... i] sont <= pivot.
	for(int j = low; j < high; j++)
	{
		if(arr[j] <= pivot)
		{
			i++;
			swap(arr[i], arr[j]); // Échanger les deux éléments
		}
	}

	// On déplace le pivot juste après les éléments inférieurs :
	swap(arr[i + 1], arr[high]);

	return i + 1; // On retourne l'indice du pivot
} // partition()

// Fonction de tri rapide (récursive) O(n log2(n))
void quickSort(vector<int> &arr, int low, int high, const int indent = 0)
{
	string spaces(indent, ' ');

	if(low < high)
	{
		// Partitionner le tableau :
		int pi = partition(arr, low, high); // pi est l'indice du pivot

		cout << spaces << "Pivot : " << arr[pi] << '\n';
		if(low <= pi - 1)
		{
			cout << spaces << "Tri de [";
			for(int k = low; k <= pi - 1; k++) cout << arr[k] << ',';
			cout << "\b]";
		}
		else
		{
			cout << spaces << "Tri de [" << arr[low] << ']';
		}
		if(pi + 1 <= high)
		{
			cout << " et de [";
			for(int k = pi + 1; k <= high; k++) cout << arr[k] << ',';
			cout << "\b]";
		}
		else
		{
			cout << " et de [" << arr[high] << ']';
		}
		cout << '\n';

		// Appel récursif pour les éléments <= pivot :
		quickSort(arr, low, pi - 1, indent + 3);

		// Appel récursif pour les éléments >= pivot :
		quickSort(arr, pi + 1, high, indent + 3);
	}
} // quickSort()

int main()
{
	vector<int> arr = {8, 3, 1, 7, 0, 10, 2};
	cout << "Tableau avant tri : ";
	for(int num : arr) cout << num << ' '; cout << '\n';

	quickSort(arr, 0, arr.size() - 1);

	cout << "Tableau après tri : ";
	for(int num : arr) cout << num << ' '; cout << '\n';

	return 0;
} // main()