3465

#include <stdio.h>
#include <iostream>
using namespace std;

void qsort (int *a1, int l, int r, int n);
void printmas (int *a1, int n);
void change (int *a, int *b);
static int c=0;

int main ()
{
    int n;
    cout<< "Input n (number of elements):"<< endl;
    cin>> n;
    int a[n];
    cout<< "Inpunt mass elements:"<< endl;
    for (int i=0; i<n; i++)
        cin>> a[i];
    cout<< "Mass before sort:"<<endl;
    printmas (a, n);
    cout<< endl<< "Mass durung sorting:"<<endl;
    qsort (a, 0, n-1, n);
    cout<< "Number of changes: "<<endl<<c<<endl<<"Mass after sort:"<<endl;
    printmas (a, n);
}

void printmas (int *a1, int n)                              //?-?, ????????? ?? ????? ??-?? ???????
{
    for (int i=0; i<n; i++)
        cout<< a1[i]<< " ";
}

void qsort ( int *a1, int l,  int r, int n)
{
    int fir=l;                                              //???????? ?? ?????? ???????
    int las=r;                                              //????????? ?? ????? ???????
    int mid=a1[(l+r)/2];                                    //????. ??-?
    while (l<r)
    {
        while (a1[l]<mid)
            l++;                                            //???????? ????? ?????????, ???? ??-? ?????? ????.
        while (a1[r]>mid)
            r--;                                            //???????? ?????? ?????????, ???? ??-? ?????? ????.
        if (l<=r)
        {
            if (a1[l]>a1[r])                                //???? ????? ?????? ???????
                {
                    change (&a1[l], &a1[r]);                //?????? ??-?? ???????
                    printmas (a1, n);                       //?????? ???????
                    cout<< endl;
                }
            l++; r--;                                       //???????? ?????????
        }
        if (l>fir)
            qsort (a1, fir, r, n);                          //???? ????? ????????? ?????????, ?? ???????? ?????????? ??????? ????? ?? ????. ??-??
        if (r<las)
            qsort (a1, l, las, n);                          //???? ?????? ????????? ?????????, ?? ???????? ?????????? ??????? ?????? ?? ????. ??-??
    }

}

void change (int *a, int *b)                                //?-?, ???????? ??-?? ?????? ???????
{
    int k = *a;
    *a=*b;
    *b = k;
    c++;
    cout<<c<<" "<<endl;
}