Листики

//Vladislav Orlov
//23.10.2014
//подсчет листьев в быстрой сортировке

#include <iostream>
#include <ctime>

using namespace std;

void quickSort(int arr[], int left, int right);
void results(int arr[]);

int pet = 0; //листики

int main()
{
    srand(time(0));

    int n = 10;
    int* a = new int[n];

    cout << "Before: ";
    for (int i=0; i<n;i++)
    {
        a[i] = rand()%100;
        cout << a[i] << " ";
    }
    cout << endl << "After: ";
    quickSort(a, 0, n-1);
    for (int i=0; i<n;i++)
    {
        cout << a[i] << " ";
    }
    cout << endl << "Petals: "<< pet << endl;
    return 0;
}

void quickSort(int arr[], int left, int right) {
    bool isPet = true; //считаем что мы листик
    pet++; //увеличиваем количество


    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {
        while (arr[i] < pivot)
                i++;
        while (arr[j] > pivot)
                j--;
        if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
        }
    };

    if (left < j)
    {
        quickSort(arr, left, j);        //оказывается мы не листик :(
        pet--;                          //удаляем себя из листиков
        isPet = false;                  //мы больше не листик
    }
    if (i < right)
    {
        if (isPet)                      //защита от повторного удаления
        {
            pet--;
            isPet = false;
        }
        quickSort(arr, i, right);
    }
}