#include <iostream>
#include <ctime>
//#include <cstdlib>

using namespace std;

void InsertionSort(int** arr, const int str, const int stlb){
int temp, item, counter=0;
for (int i=0; i<str; i++){
    for (int j=1; j<stlb; j++){
            temp=arr[i][j];
            item=j-1;
    while((item>=0)&&(arr[i][item]>temp))
    {
        counter++;
        arr[i][item+1] = arr[i][item];
        arr[i][item] = temp;
        item--;
    }

    }
} cout<< endl <<"Затрачено шагов: " <<counter<<endl;
}

void BubbleSort(int** arr, const int str, const int stlb){
    int counter=0;
    for (int z=0; z<stlb; z++){
        for (int i=0; i<str; i++){
            for (int j=0; j<stlb-1; j++){
                if (arr[i][j]>arr[i][j+1]){
                    counter++;
                    swap(arr[i][j+1],arr[i][j]);
                }
            }
        }
    } cout<< endl <<"Затрачено шагов: " <<counter<<endl;
}

/*void BubbleSort(char** arr, const int str, const int stlb){
    int counter=0;

}*/


int main(){
setlocale(LC_ALL,"rus");
//srand(time(0));
int N, M;
clock_t start;
double duration;
cout << "Ввод количества строк: "; cin >> M;
cout << "Ввод количества столбцов: "; cin >> N;
int** matrix;
matrix = new int*[M];
for (int i=0; i<M; i++)
    matrix[i]=new int[N];

for (int i=0; i<M; i++){
    for (int j=0; j<N; j++){
        matrix[i][j]=rand()%100;
        cout << matrix[i][j]<<" ";
        //cout << "Введите элемент матрицы: ";
        //cin >> matrix[i][j];
        } cout << endl;
}

/*cout << "Изначальная матрица: " << endl;
for (int i=0; i<M; i++){
    for (int j=0; j<N; j++){
       cout <<matrix[i][j]<< " ";
        } cout << endl;
}*/

cout << "Выберите сортировку: 1. Вставками 2. Пузырёк";
int key; cin >> key;
switch (key){
    case 1:
    start = clock();
    InsertionSort(matrix,M,N);
    duration = (double)(clock()-start)/CLOCKS_PER_SEC;

    cout << "Отсортированная матрица: " << endl;
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
        cout << matrix[i][j] << " ";
    } cout << endl;
    }
    cout << duration<<endl;
    break;
    case 2:
    start = clock();
    BubbleSort(matrix,M,N);
    duration = (double)(clock()-start)/CLOCKS_PER_SEC;

    cout << "Отсортированная матрица: " << endl;
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
        cout << matrix[i][j] << " ";
    } cout << endl;
    }
     cout << duration<<endl;
    break;

}
return 0;
}