#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int i, M = 0, C = 0;

void FillInc(int A[], int n) {
    for (i = 0; i < n; i++) {
        A[i] = i + 1;
    }
}

void FillDec(int A[], int n) {
    for (i = 0; i < n; i++) {
        A[i] = n - i;
    }
}

void FillRand(int A[], int n) {
    srand(time(NULL));
    for (i = 0; i < n; i++) {
        A[i] = rand() % n;
    }
}


void PrintMas(int A[], int n) {
    for (i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
}

void SelectSort(int A[], int n)
{
    M = 0, C = 0;
    int i,j,k,t;
    for (i = 0; i < n-1; i++ ) {
        k = i;
        for( j=i+1; j<n; j++){
            C++;
            if (A[j]<A[k])k=j;
        }
        t=A[i];
        A[i]=A[k];
        A[k]=t;
        M+=3;
    }
}

void BubbleSort(int A[], int n) {
    int j, min, temp;
    M = 0; C = 0;
    for (i = 0; i < n - 1; i++) {
        for (j = n - 1; j > i; j--) {
            C += 1;
            if (A[j] < A[j - 1]) {
                temp = A[j];
                A[j] = A[j - 1];
                A[j - 1] = temp;
                M += 3;
            }
        }
    }
}
void ShakerSort(int A[], int n) {
 M = 0, C = 0;
 int left,right,i,j,k,w;
 left=0;
 right=n-1;
 k=n-1;
 do {
  for(j = right; j > left; j-- ){
   C ++;
   if (A[j] < A[j-1]) {
    w = A[j];
       A[j] = A[j-1];
      A[j-1] = w;
       k = j;
       M += 3;
   }
  }
  left = k;
  for(j = left; j < right; j++ ){
   C ++;
      if(A[j] > A[j+1]){
       w = A[j];
       A[j] = A[j+1];
       A[j+1] = w;
       k = j;
       M +=3;
   }
  }
  right = k;
 }
 while(left < right);
}
void InsertSort(int A[], int n) {
    M = 0, C = 0;
    int i,t,j;
    for(i=1; i<n; i++) {
        M++;
        t=A[i];
        j=i-1;
        while(j>=0 && (C++, t<A[j])) {
            M++;
            A[j+1]=A[j];
            j=j-1;
        }
        M++;
        A[j+1]=t;
    }
}

int main() {
    int n;
    int w;

    n = 10;
    int A[n];

    printf("Возрастающий массив: ");
    FillInc(A, n);
    PrintMas(A, n);

    printf("\n");
    printf("Отсортированный массив: ");
    InsertSort(A, n);
    PrintMas(A, n);
    printf("\n ");

    printf("\n");
    printf("M = %d  C = %d", M, C);
    printf("\n");
    printf("M + C = %d", M + C);
    printf("\n");

    printf("\n");
    printf("Убывающий массив: ");
    FillDec(A, n);
    PrintMas(A, n);

    printf("\n");
    printf("Отсортированный массив: ");
    InsertSort(A, n);
    PrintMas(A, n);
    printf("\n");

    printf("\n");
    printf("M = %d  C = %d", M, C);
    printf("\n");
    printf("M + C = %d", M + C);
    printf("\n");

    printf("\n");
    printf("Случайный массив: ");
    FillRand(A, n);
    PrintMas(A, n);

    printf("\n");
    printf("Отсортированный массив: ");
    InsertSort(A, n);
    PrintMas(A, n);
    printf("\n");

    printf("\n");
    printf("M = %d  C = %d", M, C);
    printf("\n");
    printf("M + C = %d", M + C);
    printf("\n\n------------------------------1 Table-------------------------------------------------------\n\n");

    for (n = 100; n < 501; n += 100) {
        w = 2 * (n * n - n) / 2 + 2 * n - 2;
        int B[n];
        printf("N = %d", n);
        printf(" | T = %d", w);
        FillDec(B, n);
        InsertSort(B, n);
        printf(" | Dec: %d", M + C);
        FillRand(B, n);
        InsertSort(B, n);
        printf(" | Rand: %d", M + C);
        FillInc(B, n);
        InsertSort(B, n);
        printf(" | Inc: %d", M + C);
        printf("\n\n");

    }
    printf("---------------------------------------------------------------------------------------------------");
    printf("\n\n------------------------------2 Table-------------------------------------------------------\n\n");
    for (n = 100; n < 501; n += 100) {
        int B[n];
        printf("N = %d", n);
        FillRand(B, n);
        SelectSort(B, n);
        printf(" | Select: %d", M + C);
        FillRand(B, n);
        BubbleSort(B, n);
        printf(" | Bouble: %d", M + C);
        FillRand(B, n);
        ShakerSort(B, n);
        printf(" | Shaker: %d", M + C);
        FillRand(B, n);
        InsertSort(B, n);
        printf(" | Insert: %d", M + C);
        printf("\n\n");

    }
     printf("---------------------------------------------------------------------------------------------------");
    return 0;

}