QuickSort.cpp

#include <iostream>

using namespace std;

template <typename T> size_t partition(T arr[], const size_t& begin, const size_t& end){

    size_t p = begin;
    for(size_t i = begin; i<= end; i++){

        if(arr[i] <= arr[end]){
            swap(arr[i], arr[p]); // cambia quel valore dell array che e <= con pivot
            p++; // aumenta solo qua
        }
    }
    return p-1;
}

template <typename T> void quicksort(T arr[], const size_t& begin, const size_t& end){ // 2 chiamata

    if ( begin >= end){
        return;
    }
    size_t p = partition(arr, begin, end);

    cout << "indice pivot: " << p << endl;

    if(p>0)
    quicksort(arr, begin, p-1);
    quicksort(arr, p+1, end);
}

template <typename T> void quicksort(T arr[], const size_t& size){
    quicksort(arr, 0, size-1); // pivot come ultimo elelmento 1 chiamaat
}


int main(){

    size_t size = 8;
    int arr[8] = {9,3,2,4,6,8,0,5};

    quicksort(arr, size);
    for(auto& k : arr){
        cout << k << endl;

        cout << endl;

    }



}