#include<iostream>
using namespace std;
int pos_pivote(int arr[], int ini, int fin){
    int pivote = arr[fin];
    int i = ini;
    for (int j=ini; j<fin; j++){
        if (arr[j]<pivote){
            swap(arr[i], arr[j]);
            i++;
            // swap(arr[i++], arr[j]); // for one-line lovers
        }
    }
    swap(arr[fin], arr[i]);
    return i;
}
void quick_sort(int arr[], int ini, int fin){
    int i;
    if (ini<fin){
        i = pos_pivote(arr, ini, fin);
        quick_sort(arr, ini, i-1);
        quick_sort(arr, i+1, fin);
    }
}
int main(){
    int arr[] = {3,5,8,7,2,1,6};
    quick_sort(arr, 0, 6);
    for (int i=0; i<7; i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

#include<iostream>
using namespace std;
template<typename T>
int pos_pivote(T arr[], int ini, int fin){
    T pivote = arr[fin];
    int i = ini;
    for (int j=ini; j<fin; j++){
        if (arr[j]<pivote){
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[fin], arr[i]);
    return i;
}
template<typename T>
void quick_sort(T arr[], int ini, int fin){
    int i;
    if (ini<fin){
        i = pos_pivote(arr, ini, fin);
        quick_sort(arr, ini, i-1);
        quick_sort(arr, i+1, fin);
    }
}
int main(){
    int arri[] = {9, 9, 10, 11, 9, 8, 9};
    double arrd[] = {9.4, 9.6, 10.5, 11.5, 9, 8, 9};
    
    int ni = sizeof(arri)/sizeof(arri[0]);
    cout<<"ordenando "<<ni<<" elementos de arri..."<<endl;
    quick_sort(arri, 0, ni-1);
    for (int i=0; i<ni; i++){
        cout<<arri[i]<<" ";
    }
    cout<<endl;
    int nd = sizeof(arri)/sizeof(arri[0]);
    cout<<"ordenando "<<nd<<" elementos de arrd ..."<<endl;
    quick_sort(arrd, 0, nd-1);
    for (int i=0; i<nd; i++){
        cout<<arrd[i]<<" ";
    }
    cout<<endl;
    return 0;
}