#include <iostream>
#include <cmath>
#include <locale.h>
#include <ctime>
#include <conio.h>

using namespace std;

void quick_sort(int**, int, int, int);

int main() {
    setlocale(LC_ALL, "RUS");
    srand(time(NULL));
    int n, m;
    cout << "Введите кол-во строк: "; cin >> n;
    cout << "Введите кол-во столбцов: "; cin >> m;
    int **matrix = new int *[n];
    for (int i = 0; i < n; ++i)
        matrix[i] = new int[m];
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        matrix[i][j] = rand() % 50 + 1;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
        cout << matrix[i][j] << " ";
        if (j == m - 1) { cout << endl; }
    }
    cout << endl << endl;
    //==============QUICK_SORT=====================
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j += m)
            quick_sort(matrix, i, 0, m-1);
        //==============QUICK_SORT=====================
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cout << matrix[i][j] << " ";
            if (j == m - 1) { cout << endl; }
        }
    _getch();
}

void quick_sort(int **matrix, int rows, int low, int high) {
    //low == i; high == m
    int i = low, j = high, med_ind = (low + high) / 2, med = matrix[rows][med_ind];
    do {
        while (matrix[rows][i] < med) {++i;}
        while (matrix[rows][j] > med) {--j;}
        if (i <= j) {
            if (matrix[rows][i] > matrix[rows][j]) {
                matrix[rows][i] = matrix[rows][i] ^ matrix[rows][j];
                matrix[rows][j] = matrix[rows][i] ^ matrix[rows][j];
                matrix[rows][i] = matrix[rows][i] ^ matrix[rows][j];
                cout << med << " " << i << " " << j << endl;
                for (int x = 0; x < 6; ++x) { cout << matrix[rows][x] << " "; }
            }
            i++; j--;
        }
    }
    while (i > j);
    cout << endl << low << " " << i << " " << j << endl;
    /*if (low < j) {quick_sort(matrix, 0, low, j);}
    if (i < high) {quick_sort(matrix, 0, i, high);}
    */
}