#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <nmmintrin.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <cmath>
#include <climits>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <sstream>
#include <winbgim.h>
using namespace std;
const int WID = 800, HIGH = 600;
void FillInc(int n,int *a)
{
    for (int i = 0; i < n;++i)
    {
        a[i] = i;
    }
}
void FillDec(int n,int *a)
{
    for (int i = n; i > 0;i-- )
    {
        a[n-i] = i;
    }
}
void drawLine(int moveToX, int moveToY, int drawX, int drawY, int color, int textX, int textY, char *name)
{
    moveto(moveToX, moveToY);
    setcolor(color);
    lineto(drawX, drawY);
    outtextxy(textX, textY, name);
}
void FillRand(int n,int *a)
{
    for (int i = 0;i < n;++i)
    {
        a[i] = rand() % n;

    }
 }
void CheckSum(int n, int *a)
{
    int x = 0;
    for(int i = 0; i < n;++i)
    {
        x+=a[i];
    }
    cout << endl << x;
}
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void ShakerSort(int m, int *a)
{
    int i, j, k,M = 0,C = 0;
    for(i = 0; i < m;)
    {
      for(j = i+1; j < m; j++)
      {
          C++;
         if(a[j] < a[j-1])
         {
            swap(&a[j], &a[j-1]);
            M+=3;
         }
      }
    m--;
    for(k = m-1; k > i; k--)
    {
        ++C;
        if(a[k] < a[k-1])
        {
            swap(&a[k], &a[k-1]);
            M+=3;
        }
    }
    i++;
   }
    cout << "M(fact) = " << M << " C(fact) = " << C << endl;
}
int MCShakerSort(int m, int *a)
{
    int i,sum = 0, j, k,M = 0,C = 0;
    for(i = 0; i < m;)
    {
      for(j = i+1; j < m; j++)
      {
          C++;
         if(a[j] < a[j-1])
         {
            swap(&a[j], &a[j-1]);
            M+=3;
         }
      }
    m--;
    for(k = m-1; k > i; k--)
    {
        ++C;
        if(a[k] < a[k-1])
        {
            swap(&a[k], &a[k-1]);
            M+=3;
        }
    }
    i++;
   }
    sum = M + C;
    return sum;
}
void SSort(int n, int *a)
{
    int i, j, mina, M=0, C=0;
    for (i = 0; i < n-1; i++)
    {
        mina = i;
        for (j = i+1; j < n; j++)
        {
            ++C;
            if (a[j] < a[mina])
            mina = j;
        }
    if(mina!=i)
     {
       M+=3;
       swap(a[mina], a[i]);
     }
   }
    cout<<endl<<"(fact)C = "<< C<<" (fact) M = "<< M;
 }
 void CheckMC(int n)
{
    int m,c;
    m = pow(n,2);
    c = (pow(n,2)-n)/2;
    cout << "M = " << m << " C = " << c << endl;
}
 void ShakerCheckMC(int n)
{
    int m,c;
    c = (pow(n,2)-n)/2;
    m = 3*(pow(n,2)-n)/2;
    cout << "M = " << m << " C = " << c << endl;
}
void RunNumber(int n,int *a)
{
    int x = 1;
    int null = a[0];
    for (int i = 1; i < n;i++)
    {
        if (a[i] < null)
        {
            x++;
        }
        null = a[i];
    }
    cout << endl << x;
}
void PrintMas(int n,int *a)
{
  for (int i = 0; i < n;++i)
  {
    cout << a[i]<<" ";
  }
}
void BubbleSort(int n, int *a)
{
  int i, j;
  int c = 0, m = 0;
  for (i = 0; i < n-1; i++)
    for (j = 0; j < n-i-1; j++)
    {
     ++c;
     if (a[j] > a[j+1])
     {
      m+=3;
      swap(&a[j], &a[j+1]);
    }
  }
  cout << endl << "M(fact) = " << m << " " <<  "C(fact) = " << c << " ";
}
int MCBubbleSort(int n, int *a)
{
  int i, j,sum;
  int c = 0, m = 0;
  for (i = 0; i < n-1; i++)
    for (j = 0; j < n-i-1; j++)
    {
     ++c;
     if (a[j] > a[j+1])
     {
      m+=3;
      swap(&a[j], &a[j+1]);
    }

  }
  sum = c + m;
  return sum;

}
void PrintTabl()
{
  int m,c,n,sum = 0;
  int *a = new int[n];
  n = 100;
  int RandSum,IncSum,DecSum;
  int SRandSum, SIncSum,SDecSum;
  cout << endl << "| n |        MFact + CFact Bubble    |     MFact + CFact Shaker     |" << endl;
  cout << "|   |  ybiv    |   Rand   |  vozr    |  ybiv  |   Rand   |    vozr  |" << endl;
  for (int i = 1;i <= 5;++i)
  {
    n = i * 100;
    FillRand(n,a);
    RandSum = MCBubbleSort(n,a);
    FillDec(n,a);
    DecSum = MCBubbleSort(n,a);
    FillInc(n,a);
    IncSum = MCBubbleSort(n,a);
    FillRand(n,a);
    SRandSum = MCShakerSort(n,a);
    FillDec(n,a);
    SDecSum = MCShakerSort(n,a);
    FillInc(n,a);
    SIncSum = MCShakerSort(n,a);
    cout << "|" << n << "| " << " " << setw(8)<< DecSum << "| " << setw(8) <<
    RandSum << " | " << setw(8) << IncSum << " |" << setw(8)<< SDecSum << "| " << setw(8) <<
    SRandSum << " | " << setw(8) << SIncSum << " |" << endl ;
  }
}
void GraphText(int x1, int y1, int x2, int y2, int color, int textX, int textY, char *name)
{
    setcolor(color);
    bar(x1,y1,x2,y2);
    outtextxy(textX, textY, name);
}
int Graph()
{
    double y1;
    int x1;
    int *a = new int[x1];
    double x2;
    x2 = x1;
    initwindow(WID, HIGH);
    moveto(WID / 2, HIGH / 2);
    for (x1 = -WID; x1 < WID; x2 += 0.1)
    {
        FillRand(x1,a);
        y1 = MCBubbleSort(x1,a);
        setcolor(4);
        x2 = x1;
        x1+=1;
        lineto((WID / 2) + (x1 * 10), (HIGH / 2) - (y1 * 10));
    }
    for (x1 = -WID; x1 < WID; x2 += 0.1)
    {
        FillRand(x1,a);
        y1 = MCShakerSort(x1,a);
        setcolor(3);
        x2 = x1;
        x1+=1;
        lineto((WID / 2) + (x1 * 10), (HIGH / 2) - (y1 * 10));
    }
    drawLine(0, HIGH / 2, WID, HIGH / 2, 15, WID - 20, HIGH / 2 + 10, "X");
    drawLine(WID / 2, 0, WID / 2, HIGH, 15, WID / 2 + 10, 0, "Y");
    GraphText(8, 50, 33, 75, 4, 47, 63, "Bubble Sort");
    GraphText(8, 88, 33, 113, 3, 47, 99, "Shaker Sort");
    getch();
    closegraph();
    return 0;
}
int prompt_menu_item()
{
    int variant;
    cout << "Âûáåðèòå ïóíêò ìåíþ \n" << endl;
    cout << "1. \n"
         << "2. \n"
         << "3. \n"
         << "4. Shaker Sort\n"
         << "5. \n"
         << "6. \n"
         << "7. " << endl;
    cout << ">>> ";
    cin >> variant;
    return variant;
}
int main()
{
    int n;
    int *a = new int[n];
    setlocale(LC_ALL, "Russian");
/*  cout << "Ââåäèòå ðàçìåð ìàññèâà: ";
    cin >> n;
    int variant = prompt_menu_item();
    switch (variant)
    {
        case 1:
        {
            break;
        }

        case 2:
        {
            break;
        }
        case 3:
        {
            break;
        }

        case 4:
        {
            FillRand(n,a);
            PrintMas(n,a);
            cout << endl;
            ShakerCheckMC(n);
            cout << "Sorting..." << endl;
            ShakerSort(n,a);
            PrintMas(n,a);
            PrintTabl();
            break;
        }
        case 5:
        {
            break;
        }
        case 6:
        {
            break;
        }
        case 7:
        {
           break;
        }
    }
   */
    cout << "N:=  ";
    cin >> n;
    FillDec(n,a);
    FillRand(n,a);
    PrintMas(n,a);
    cout << endl;
    ShakerCheckMC(n);
    cout << "Sorting..." << endl;
    ShakerSort(n,a);
    PrintMas(n,a);
    PrintTabl();
    Graph();
}