#include <iostream>
using namespace std;
int tab[10]={1,2,13,3,15,4,6,13,5,5};
void swap(int *tab, int i, int j)
{
    int tmp=tab[i];
    tab[i]=tab[j];
    tab[j]=tmp;
}
void fix_table(int *tab, int pivot, int l, int p)
{
    while(l<p)
    {
        while(tab[l]==pivot)l++;
        while(tab[p]!=pivot)p--;
        swap(tab,p,l);
        l++;
        p--;
    }
}
int partition(int *tab, int l, int p, int &counter)
{
    int i = l-1;
    int pivot = tab[p];
    for (int j=l; j<p; j++)
    {
        if(tab[j]<pivot)
        {
            i++;
            swap(tab,i,j);
        }
        else if(tab[j]==pivot)counter++;
    }
    i++;
    swap(tab,i, p);
    fix_table(tab,tab[i],i,p);
    return i;
}
void quick_sort(int *tab, int l, int p)
{
    int counter=0;
    if(l<p)
    {
        int q = partition(tab, l, p, counter);
        quick_sort(tab, l, q-1);
        quick_sort(tab,q+counter+1, p);
    }
}
int main() {
    quick_sort(tab,0,9);
    int cou=0;
   // partition(tab,0,9,cou);
    cout << endl;
    for(int i : tab)cout << i << endl;
    return 0;
}