Algoritmi lezione 19 - Quick Sort, parte A

#include <iostream>

using namespace std;


int partiziona(int v[], int inizio, int fine)
{
  cout << string(40, '*') << endl;

  cout << "partiziono da " << inizio <<" a " << fine << endl;
    int pivot = v[inizio];

    int cont = 0;
    for (int i = inizio + 1; i <= fine; i++) {
        if (v[i] <= pivot)
            cont++;
    }

    //mettiamo il pivot nella posizione che gli spetta
    int indice_pivot = inizio + cont;
    swap(v[indice_pivot], v[inizio]);
    cout << "per pivot scambio " << v[indice_pivot] << " con " << v[inizio] << endl;

    // spostiamo gli elementi più piccoli del pivot alla sua sinistra
    // e quelli più grandi alla sua destra
    int i = inizio, j = fine;

    while (i < indice_pivot && j > indice_pivot) {

        while (v[i] <= pivot) {
            i++;
        }

        while (v[j] > pivot) {
            j--;
        }

        if (i < indice_pivot && j > indice_pivot) {
      cout << "scambio " << v[i] << " con " << v[j] << endl;
            swap(v[i], v[j]);
            i++; j--;
        }
    }
    cout << string(40, '-') << "\n\n";

    return indice_pivot;
}

void quickSort(int v[], int inizio, int fine)
{

    if (inizio >= fine)
        return;


    int p = partiziona(v, inizio, fine);

  // ordina la parte a sinistra
    quickSort(v, inizio, p - 1);

    // ordina la parte a destra
    quickSort(v, p + 1, fine);
}

int main()
{

    int v[] = { 81, 98, 78, 60, 115, -3, 45, 45, 1, 10 };
    int n = 10;

    quickSort(v, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }

    return 0;
}