#include<iostream.h>
void swap(int &a, int &b) // a b
{
int t=a;
a=b;
b=t;
}
void swap(int &a, int &b, int &c) // a <= b <= c; 书 е
{
if((a>=b && b>c) || (a>b && b==c)) swap(a, c);
else if(a>b && b<c)
{
if(a<=c) swap(a,b);
else { swap(a,b); swap(b, c);}
}
else if(a<b && b>c)
{
if(a<=c) swap(b, c);
else { swap(b, c); swap(a, b);}
}
}
void swap(int A[], int a, int b, int c) // ü
{
swap(A[a], A[b], A[c]);
}
int sortcheck(int A[], int n) // λ
{
int check=0;
for(int i=0; i+1<n; i+=2)
{
if(A[i]>A[i+1]){ swap(A[i], A[i+1]); check++;} //1
if(i+2<n && A[i+1]>A[i+2]) check++; //2
}
return check;
}
void sort(int A[], int n, int r=1) // 2
{ // A R <= L <= R С С
if(2*r+1<=n)
{
swap(A, r-1, 2*r-1, 2*r);
sort(A, n, 2*r);
sort(A, n, 2*r+1);
swap(A, r-1, 2*r-1, 2*r); //
}
else if(2*r==n && A[r-1]>A[2*r-1]) swap(A[r-1],A[2*r-1]);
}
int Sort(int A[], int n) //
{
int count=0;
while(sortcheck(A, n)) // δ 1
{
int r=1;
sort(A, n, r); // 2
count ++;
}
return count; // count
}
void BinarySort(int A[], int n)
{
cout<<endl<<" "<<endl;
for(int i=0; i<n; i++)cout<<A[i]<<" ";
cout<<endl;
cout<<endl<<" "<<Sort(A,n)<<" "<<n<<" "<<endl;
cout<<endl<<" "<<endl;
for(i=0; i<n; i++)cout<<A[i]<<" ";
cout<<endl;
}
void main()
{
int A[35]={34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0};
BinarySort(A, 35);
}