/* C++ implementation of QuickSort */
#include <bits/stdc++.h>
using namespace std;
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
    cout << arr[i] << " ";
//  cout << endl;
}

int partition (int tab[], int left, int right)
{
    int pivot = tab[right]; // pivot
            cout<<"\n\n###### Pivot to: "<<pivot<<" ######"<<endl;
    int l=left;
    int r=right;

    while(true){
        while(tab[l]>pivot) ++l;
        while(tab[r]<pivot) --r;
                cout<<"\n---L: "<<l<<"  R: "<<r<<endl;

        if(l<r){

            cout<<"                         swap "<<tab[l]<< " z " <<tab[r]<<endl;
            swap(tab[l],tab[r]);
            ++l;
            --r;
                    printArray(tab, 8);

        }
        else{
            if (r==right) r--;
                    printArray(tab, 8);
                    cout<<"        r==right (koniec partycjonowania) " ;
            return r;
        }
    }
}


void quickSort(int tab[], int l, int p)
{
    if (l>=p)  return;

        int m = partition(tab, l, p);
                 cout<<"!!!!  m to: "<<m<<endl<<endl;
                 cout<<"\nquicksort1(tab,"<<l<<","<<m<<")"<<endl;
        quickSort(tab, l, m);
                //printArray(tab, 8);
                //cout<<"\ntu1\n"<<endl;
                cout<<"\nquicksort2(tab,"<<m+1<<","<<p<<")"<<endl;

        quickSort(tab, m + 1, p);
                //printArray(tab, 8);
                //cout<<"\ntu2\n"<<endl;
                cout<<endl;

}

// Driver Code
int main()
{
    int arr[] = {4,8,7,5,3,9,10,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);

    cout << "\nSorted array: \n";
    printArray(arr, n);
    return 0;
}

// This code is contributed by rathbhupendra