LIFO == TimeShift

//The source code and comment by Genius Ignat©
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
#include <iostream>       //Экран клавиатура: U I/0
#include <fstream>        //Файлы: U I/0
using namespace std;
//Основной код:
//----------------------------------------------------------------------------------------------------------------------
const long UNKNOWN_VALUE = -10; //некое значение.
const long ERROR_INDEX = -30;   //неверный индекс.
const long STACK_EMPTY = -20;   //стек пуст.
const long EQUAL_IND = -2;      //переданны одинаковые индексы.
const long NOT_RAT_MATRIX = -3; //передана не равнопроцентная матрица.
const long H = 5;               //высота матрицы.
const long W = 5;               //ширина матрицы.
const long M_ERROR = -1;         //ошибка.
const long M_OK = 0;             //всё ok.
 
/*
Массив ключей от рядов можно настроить и на другую матрицу, имеющию стандартную 
равнопроцентную структуру.
*/
//Массив ключей от рядов.
const int RAD_KEYS[] = {1,2,3,4,5};  //правильный ключ от каждого ряда.
typedef int RAT_MATRIX[H][W];        //тип матрицы.
 
/*
Набор пройденных тестов для функции transform без суффикса_2:
//----------------------------
(1)
  
    {1,2,5,4,3}
    {2,1,1,5,4}
    {1,1,2,5,3}
    {2,2,5,4,3}
    {5,4,4,3,3}
 
при: H == 5
     W == 5
 
swaps: 17
 
const int RAD_KEYS[] = {1,2,3,4,5}; 
 
//-----------------------------
(2) 
   
    {1,2,3,4,3}
    {2,1,1,3,4}
    {1,1,2,4,3}
    {2,2,4,4,3}
 
при: H == 4
     W == 5
 
swaps: 12
const int RAD_KEYS[] = {1,2,3,4}
 
Предупреждение:
Совместно алгоритм transform и transofrm_2 будут работать только на квадратных матрицах.
Если посмотреть на свойстdо равнопроцентной матрицы можно понять почему только для квадратных.
//------------------------------------------
 
(3)
    {3,3,3,4}
    {2,1,1,5}
    {1,1,2,5}
    {2,2,5,4}
    {5,4,4,3}
 
при H == 5
    W == 4 
swaps: 13
const int RAD_KEYS[] = {1,2,3,4,5};
//------------------------------------------
 
(4) 
    {1,2,3}
    {3,2,1}
    {2,1,3}
 
при H == 3
    W == 3
swaps: 5
const int RAD_KEYS[] = {1,2,3};
меньше 3x3 вообще не вижу смысла
//------------------------------------------
(5)
 
 {1,4,4,4,4,4,5,7,8,8}
 {2,2,1,1,3,3,5,7,8,8}
 {2,2,2,1,1,2,5,7,9,9}
 {4,4,4,4,4,6,7,8,9,9}
 {1,1,2,2,5,6,7,8,9,10}
 {3,3,3,3,5,6,7,8,9,10}
 {5,5,5,5,5,6,7,9,10,10}
 {2,6,6,6,6,7,8,9,10,10}
 {3,3,3,3,6,7,8,9,10,10}
 {1,1,1,2,6,7,8,9,10,10}
 
при H == 10
    W == 10
swaps: 79.
const int RAD_KEYS[] = {1,2,3,4,5,6,7,8,9,10};
 
Больше не проверял задолбался заполнять 10x10.
//---------------------------------------------
*/
/*
 
Некоторые  закономерные особенности моего алгоритма.
Количество обменов при трансформации не может быть больше чем H*W - размера самой матрицы:
Как бы не располагались элементы, обменов все равно не может быть больше H*W,
потому как алгоритм на каждом исследуемом шаге может сделать один обмен или неодного.
Мой алгоритм не делает многократных замен, в этом нет необходимости, это не сортировка.
 
Обнаружить не равно-процентную матрицу алгоритм может в процессе своего исполнения:
   во время трансформации, если матрица не равно-процентная будет возврат, 
   элементы поменяют свои места на другие, 
   потому как неправильная матрица обнаруживается во время исполнения transf. 
   Прежнее состояние можно вернуть стеком c помощью Restore.
*/
 
 
//----------------------------------------------------------------------------------------------------------------
//Структура точки матрицы
struct Point {
int x;  //позиция по x
int y;  //позиция по y
Point(): x(0),y(0){}     //инициализация по умолчанию.
Point(int v_x,int v_y):x(v_x),y(v_y){}
//действительна ли точка в системе координат([0].[0]).
inline bool point_valid(){ if(x<0||y<0)return false; return true; }  
};
 
 
static int SIZE_STACK = 0; //размер стека, переменная глобальная если используется один стек, она хранит верное знач
//----------------------------------------------------------------------------------------------------------------
//Описание узла стека.
struct Node  {
Node *next;   //для связи с узлом.
Point obj;    //Освновные данные узла стека.
};
 
 
//----------------------------------------------------------------------------------------------------------------
//Операции со стеком.
void push(Node **const top, int x , int y);            //положить в стек.
Point pop(Node **const top);                           //Извлечь из стека. 
 
//отчистить весь стек.
void Update(Node **const top){ while(*top)pop(top);  }
inline int  Get_Size(){ return SIZE_STACK; }                                  //размер стека.
inline bool isEmpty(Node *top){if(top!=NULL)return 0; else return 1;}        //проверка указателя.
 
//-----------------------------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------------------------
//Функции для работы с равнопроцентной матрицей.
//------------------------------------------------------
long m_print(RAT_MATRIX matrix, const int h , const int w);                   //вывод матрицы.
long m_input(RAT_MATRIX matrix, const int h , const int w);                   //ввод матрицы.
//------------------------------------------------------
long m_save(RAT_MATRIX matrix, const int h , const int w, const char *path);    //вывод матрицы. в файл.
long m_load(RAT_MATRIX matrix, const int h , const int w, const char *path);    //чтение матрицы из файла.
//------------------------------------------------------
long m_transform(RAT_MATRIX matrix, const int h , const int w);//упорядочивание рядов(1)
long m_transform(RAT_MATRIX matrix, const int h , const int w, Node **const top); //упорядочивание рядов(2)
long m_Restore(RAT_MATRIX matrix, const int h , const int  w, Node **const top);  //восстановить прежнее состояние рядов.
 
/*m_Restore можно применять не только для данной задачи, полный возврат назад, может
потребовать и в других похожих задачах.
*/
//Если работать со столбцами: не относится к поставленной задачи: Improvisation
long m_transform_2(RAT_MATRIX matrix, const int h , const int w);//упорядочивание рядов(1.1)
long m_transform_2(RAT_MATRIX matrix, const int h , const int w, Node **const top); //упорядочивание рядов(2.2)
 
 
/*
В функциях transform и Restore эти функции не используются, хотя могли бы я их написал позже, 
и вставлять нехочеться.
*/
//TimeShift swap. обмен под контролем  LIFO.
long T_swap(RAT_MATRIX matrix, int x_1, int y_1, int x_2, int y_2, const int h, const int w, Node **const top); //TimeShift swap.
long T_undo(RAT_MATRIX matrix, Node **const top); //отмена при помощи LIFO TimeShift
//-----------------------------------------------------------------------------------------------------------------
 
/*
Если всё прошло успешно  transform вернёт количество обменов.
Если функция transform вернула NOT_RAT_MATRIX, значит матрица не правильная, матрица даже после возрата
такого сообщения может измениться, то есть исходное расположение элементов измениться
с помощью стека матрицу можно будет возвратить обратно.
*/
 
 
//main:
int main(){
Node *top = NULL;  //всегда ссылается на вершину это указатель так сказать ресурс для функций вида **.
//матрица:
/* Та что в задании:
    {1,2,5,4,3}
    {2,1,1,5,4}
    {1,1,2,5,3}
    {2,2,5,4,3}
    {5,4,4,3,3}
*/
 
RAT_MATRIX matrix = {
    {1,2,5,4,3},
    {2,1,1,5,4},
    {1,1,2,5,3},
    {2,2,5,4,3},
    {5,4,4,3,3}
 
};
 
//-----------------------------------------------------------------
m_print(matrix,H,W);          //выводим матрицу. 
{
int count = m_transform(matrix,H,W,&top); //трансформируем матрицу в соответстиии с задачей, путь восстановления будет в стеке.
if(count==NOT_RAT_MATRIX)cout<<"error type matrix\n\n";
else cout<<"count swaps trans: "<<count<<endl<<endl;
 
cout<<"Stack_Size:  "<<Get_Size()<<endl<<endl;
//------------------------------------------
m_print(matrix,H,W);          //выводим изменённую матрицу.
int count_2 = m_Restore(matrix,H,W,&top);   //восстанавливаем исходную матрицу.
cout<<"count swaps ret: "<<count_2<<endl<<endl;
m_print(matrix,H,W);          //выводим исходную матррицу на экран.
}
 
//-----------------------------------------------------------------
//Можно откомметировать, если надо.
#if 0
{
int count = m_transform_2(matrix,H,W,&top); //трансформируем матрицу в соответстиии с задачей, путь восстановления будет в стеке.
if(count==NOT_RAT_MATRIX)cout<<"error type matrix\n\n";
else cout<<"count swaps trans: "<<count<<endl<<endl;
cout<<"Stack_Size:  "<<Get_Size()<<endl<<endl;
m_print(matrix,H,W);          //выводим изменённую матрицу.
int count_2 = m_Restore(matrix,H,W,&top);   //восстанавливаем исходную матрицу.
cout<<"count swaps ret: "<<count_2<<endl<<endl;
m_print(matrix,H,W);                        //выводим исходную матррицу на экран.
}
#endif
 
//-----------------------------------------------------------------
cout<<"Stack_Size:  "<<Get_Size()<<endl<<endl;
//Можно откомметировать, если надо.
#if 0
T_swap(matrix,0,1,3,2,H,W,&top);
m_print(matrix,H,W);          //выводим матрицу.
T_swap(matrix,0,1,0,3,H,W,&top);
m_print(matrix,H,W);          //выводим матрицу.
T_undo(matrix,&top);
m_print(matrix,H,W);          //выводим матрицу.
T_undo(matrix,&top);
m_print(matrix,H,W);          //выводим матрицу.
#endif 
Update(&top);
system("pause");
return 0;
}
 
//----------------------------------------------------------------------------------------------------------------
//Реализация функций стека.
void push(Node **const top, int x , int y){ 
//Если стек опустел или не создан.
if(*top==NULL){
Node * pv = new Node;  //создаём узел.
//Инициализируем поля стуктуры.       
pv->obj.x = x;          
pv->obj.y = y;
pv->next = NULL;       //признак дна стека.
(*top)=pv;             //записываем адрес созданного узла в указатель вершины стека.
SIZE_STACK++;
return ;
}
else  {  
Node * pv = new Node;  //создаём узел.
//Инициализируем поля стуктуры.       
pv->obj.x = x;          
pv->obj.y = y;
pv->next = (*top);  //записываем адрес нынешней вершины.
(*top) = pv;        //созданный узел становится новой вершиной стека, связь с предыдущей верниной выставлена.
SIZE_STACK++;
return ;
}
 
}
 
//---------------------------------------------------------------------
//Извлечь из стека. 
Point pop(Node **const top){     
Node *tmp = (*top);     //получаем адрес узла, который сейчас на вершине.
//Если узел существует !=NULL
if(tmp){
(*top)=(*top)->next;    //на вершину заносим предпоследний.
Point obj = tmp->obj;   //считываем данные с узла.
delete tmp;             //удаляем узел, с вершины.
SIZE_STACK--;
return obj;             //возврщаем полученные данные.
}
Point def_obj(UNKNOWN_VALUE,UNKNOWN_VALUE);   //стека не существует.
return def_obj;
}
 
 
//---------------------------------------------------------------------
//вывод матрицы.
long m_print(RAT_MATRIX matrix, const int h , const  int w){
 
    for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++){
        cout<<matrix[i][j]<<' ';
        }
        cout<<endl;
    }
cout<<endl;
return M_OK;
}
 
//ввод матрицы.
long m_input(RAT_MATRIX matrix, const int h , const int w){
 
    for( int i = 0 ; i < h ; i++ )
         for( int j = 0 ; j < w ; j++){
                 cout<<matrix[i][j]<<' '; 
                 cin>>matrix[i][j];
                 }
 
cout<<endl;
return M_OK;
}
 
//вывод матрицы. в файл.
long m_save(RAT_MATRIX matrix, const int h , const int w, const char *path){    
ofstream obj_save(path);
if(!obj_save)return M_ERROR;
 
for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++){
 
        obj_save<<matrix[i][j];
        }
 
    }
 
return M_OK;
}
//чтение матрицы из файла.
long m_load( RAT_MATRIX matrix, const int h , const int w, const char *path){
ifstream obj_load(path);
if(!obj_load)return M_ERROR;
for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++){
        if(obj_load.eof())break;
        obj_load>>matrix[i][j];
        }
    }
 
return M_OK;
}
 
 
 
//упорядочивание рядов(1).
long m_transform(RAT_MATRIX matrix, const int h , const int w){
 
 
int i(0),j(0);
int counter = 0;
cout<<"Work trans Start---------------------------------------\n";
 
 
//переходим к очередной строке
  for( i = 0 ; i < h ; i++ ){
 
      //переходим к очередному столбцу
      for( j = 0; j < w ; j++ ){
 
//Если элемент в своём ряду.
if(matrix[i][j]==RAD_KEYS[i])
{
//-----------------------------
//-----------------------------
}   
 
//Если элемент не в своем ряду.
if(matrix[i][j]!=RAD_KEYS[i]){
 
int st_jump = j;
bool found = false;
        //Ищем элемент подходящий под этот ряд.
    for(int k = i ; k < h; k++ ){
 
             for( int r = st_jump; r < w; r++ ) {
 
                    if(matrix[k][r]==RAD_KEYS[i]){
 
                    //swap.
                    int tmp = matrix[k][r];
                    matrix[k][r]=matrix[i][j];
                    matrix[i][j] = tmp;
                    r=w; //выход.
                    k=h; //выход.
                    found = true;
                
//-----------------------------
m_print(matrix,h,w); //показываем результат работы.
//-----------------------------
counter++;
                    } // if found 
 
             }//int r = i
 
         st_jump = 0;
 
        }//int k = i
if(found==false)return NOT_RAT_MATRIX; 
 
 
 
     }  //if !=key
 
 
 
 
 
     } //for( j = 0;
 
 }  //for( i = 0
 
 
cout<<"Work trans End---------------------------------------\n";
return counter;
}
//----------------------------------------------------------------------
//упорядочивание рядов(2)
long m_transform(RAT_MATRIX matrix, const int h , const int w, Node **const top){
 
int i(0),j(0);
int counter = 0;
 
cout<<"Work trans Start---------------------------------------\n";
//переходим к очередной строке
for( i = 0 ; i < h ; i++ ){
 
      //переходим к очередному столбцу
      for( j = 0; j < w ; j++ ){
      
//Если элемент в своём ряду.
if(matrix[i][j]==RAD_KEYS[i])
{
//-----------------------------
//-----------------------------
}   
 
//Ищем элемент подходящий под этот ряд.
if(matrix[i][j]!=RAD_KEYS[i]){
 
int st_jump = j;
bool found = false;
 
    for(int k = i ; k < h; k++ ){
 
             for( int r = st_jump; r < w; r++ ) {
                    
                    if(matrix[k][r]==RAD_KEYS[i]){
                    //swap.
                    int tmp = matrix[k][r];
                    matrix[k][r]=matrix[i][j];
                    matrix[i][j] = tmp;
push(top,k,r);      //запоминаем x y.
push(top,i,j);      //запоминаем x y.
                    r=w; //выход.
                    k=h; //выход.
                    found = true;
//-----------------------------
m_print(matrix,h,w); //показываем результат работы.
//-----------------------------
counter++;
                    }  //if found
 
             }//int r = i
 
        st_jump = 0;
 
        }//int k = i
 
if(found==false)return NOT_RAT_MATRIX;  //какой то элемент не найден значит матрица не равнопроцентная
        
 
 
    }  //if !=Key
 
 
 
 
    }  //for( j = 0;
 
 }  //for( i = 0
 
 
cout<<"Work trans End---------------------------------------\n";
return counter;
}
 
 
//--------------------------------------------------------------
/*Возврат элементов на прежние места, не за постоянное время. */
long m_Restore(RAT_MATRIX matrix, const int h , const int  w, Node **const top){
if(isEmpty(*top))return STACK_EMPTY;
int count = 0;  
cout<<"Work restore Start---------------------------------------\n";
while(*top){
    Point obj_1 = pop(top);  
    Point obj_2 = pop(top);
    int tmp = matrix[obj_1.x][obj_1.y];
    matrix[obj_1.x][obj_1.y] = matrix[obj_2.x][obj_2.y];
    matrix[obj_2.x][obj_2.y] = tmp;
    m_print(matrix,h,w);
    count++;
}
cout<<"Work restore End---------------------------------------\n";
return count;
}
//----------------------------------------------------------------------------------------------------------
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------------
//Если работать со столбцами:-------------------------------------------------------------------------------
//упорядочивание рядов(1.1)
long m_transform_2(RAT_MATRIX matrix, const int h , const int w){
 
int i(0),j(0);
int counter = 0;
cout<<"Work trans(2) Start---------------------------------------\n";
//переходим к очередной строке
  for( i = 0 ; i < w ; i++ ){
 
      //переходим к очередному столбцу
      for( j = 0; j < h ; j++ ){
 
//Если элемент в своём ряду.
if(matrix[j][i]==RAD_KEYS[i])
{
//-----------------------------
//-----------------------------
}   
//Ищем элемент подходящий под этот ряд.
if(matrix[j][i]!=RAD_KEYS[i]){
int st_jump = j;
bool found = false;
    for(int k = i ; k < w; k++ ){
 
             for( int r = st_jump; r < h; r++ ) {
 
                    if(matrix[r][k]==RAD_KEYS[i]){
                    //swap.
                    int tmp = matrix[r][k];
                    matrix[r][k]=matrix[j][i];
                    matrix[j][i] = tmp;
                    r=h; //выход.
                    k=w; //выход.
                    found = true;
//-----------------------------
m_print(matrix,h,w); //показываем результат работы.
//-----------------------------
counter++;
                
                    }  //if found
 
             }//int r = i
 
 
         st_jump = 0;
        }//int k = i
if(found==false)return NOT_RAT_MATRIX;  
    }  //if !=key
 
    }  //for( j = 0;
 
 }  //for( i = 0
 
 
 
cout<<"Work trans(2) End---------------------------------------\n";
return counter;
}
 
 
//упорядочивание рядов(2)
long m_transform_2(RAT_MATRIX matrix, const int h , const int w, Node **const top){
 
int i(0),j(0);
int counter = 0;
cout<<"Work trans(2) Start---------------------------------------\n";
//переходим к очередной строке
  for( i = 0 ; i < w ; i++ ){
 
      //переходим к очередному столбцу
      for( j = 0; j < h ; j++ ){
 
//Если элемент в своём ряду.
if(matrix[j][i]==RAD_KEYS[i])
{
//-----------------------------
//-----------------------------
}   
//Ищем элемент подходящий под этот ряд.
if(matrix[j][i]!=RAD_KEYS[i]){
int st_jump = j;
bool found = false;
        for(int k = i ; k < w; k++ ){
 
             for( int r = st_jump; r < h; r++ ) {
                    if(matrix[r][k]==RAD_KEYS[i]){
                    //swap.
                    int tmp = matrix[r][k];
                    matrix[r][k]=matrix[j][i];
                    matrix[j][i] = tmp;
push(top,j,i);      //запоминаем x y
push(top,r,k);      //запоминаем x y
                    r=h; //выход.
                    k=w; //выход.
                    found = true;
//-----------------------------
m_print(matrix,h,w); //показываем результат работы.
//-----------------------------
counter++;
                    
                    }  //if //if found
             }//int r = i
         st_jump = 0;
        }//int k = i
 
        if(found==false)return NOT_RAT_MATRIX;  //какой то элемента не найден значит матрица не равнопроцентная
        
 
    }  //if !=key
 
 
    }  //for( j = 0;
 
 }  //for( i = 0
 
 
cout<<"Work trans(2) End---------------------------------------\n";
return counter;
}
 
 
//-----------------------------------------------------------------------------------------------------------
//TimeShift swap. обмен под контролем LIFO.
long T_swap(RAT_MATRIX matrix, int x_1, int y_1, int x_2, int y_2,const int h, const int w, Node **const top){
//-----------------------------------------
if((x_1==x_2)&&(y_1==y_2))return EQUAL_IND;
if((x_1>=w||x_2>=w)||(x_1<0||x_2<0)) return ERROR_INDEX ;
if((y_1>=h||y_2>=h)||(y_1<0||y_2<0)) return ERROR_INDEX ;
//-----------------------------------------
cout<<"TimeShift swap\n";   
int tmp = matrix[x_1][y_1];
matrix[x_1][y_1] = matrix[x_2][y_2];
matrix[x_2][y_2] = tmp;
push(top,x_1,y_1);
push(top,x_2,y_2);
return M_OK;
}
//отема при помощи LIFO.
long T_undo(RAT_MATRIX matrix, Node **const top){
if(isEmpty(*top))return STACK_EMPTY;
cout<<"Undo\n";
Point obj_1 = pop(top);
Point obj_2 = pop(top);
if(obj_1.point_valid()&&obj_2.point_valid()){
int tmp = matrix[obj_1.x][obj_1.y];
matrix[obj_1.x][obj_1.y] = matrix[obj_2.x][obj_2.y];
matrix[obj_2.x][obj_2.y] = tmp;
}
return M_OK;
}

#include <iostream>
using namespace std;
 
static int size = 0;
 
 
struct Node {
Node *next;
int index;
};
void push(Node**top, int idx){
    if(*top==NULL){
     Node * pv =new Node;
     pv->index=idx;
     pv->next = NULL;
     (*top)=pv;
     size++;
     return ;
    }
    else {
     Node *pv =new Node;
     pv->index=idx;
     pv->next = (*top);
     (*top)=pv;
     size++;
     return ;
    }
 
}
 
int pop(Node **top){
Node *tmp = (*top);
if(tmp){
int t = tmp->index;
(*top)=(*top)->next;
delete tmp;
size--;
return t;
}
return -1; 
}
 
 
 
int main(){
 
Node *top = NULL;
int count = 0;
const int H = 5;
const int W = 5;
 
int matrix[H][W] = {
    {1,2,5,4,3},
    {2,1,1,5,4},
    {1,1,2,5,3},
    {2,2,5,4,3},
    {5,4,4,3,3}
};
 
 
  int *mas = &matrix[0][0];
  for( int i = 0 ; i < (H*W)-1; i++ ){
        for( int j = i + 1; j<H*W; j++){
 
        if(mas[j]<mas[i]){
        int tmp = mas[i];
        mas[i]=mas[j];
        mas[j]=tmp;
        push(&top,i);
        push(&top,j);
count++;
cout<<"Swap: "<<count<<endl;
for( int k = 0 ; k < H ; k++){
    for(int p = 0 ; p < W; p++){
    cout<<matrix[k][p]<<' ';
    }
cout<<endl;
}
cout<<endl;
 
        }   
 
    }
}
 
 
cout<<"Size stack: "<<size<<endl; 
cout<<"Swaps: "<<count<<endl;
char c;
cout<<"Continue : ";cin>>c;
cout<<endl;
cout<<endl;
 
count = 0;
 
while(top){
int index1 = pop(&top);
int index2 = pop(&top);
int tmp = mas[index1]; 
mas[index1] = mas[index2];
mas[index2] = tmp;
count++;
cout<<"Swap: "<<count<<endl;
for( int k = 0 ; k < H ; k++){
    for(int p = 0 ; p < W; p++){
    cout<<matrix[k][p]<<' ';
    }
cout<<endl;
}
cout<<endl;
 
}
 
cout<<"Size stack: "<<size<<endl; 
cout<<"Swaps: "<<count<<endl;
cout<<endl;
system("pause");
return 0;
}

//The source code and comment by Genius Ignat©
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <stdlib.h>
#include <stdio.h>
 
//Тестирование алгоритма придуманного Genius Ignat ©: 
//Название алгоритма: ONE_SWAP THIS_IS_THIS ©  Genius Ignat ©. 
//Выравнивающий алгоритм для равно-процентной матрицы........
 
//Алгоритм для упорядочивания равнопроцентных матриц.
//Количество обменов(блоков памяти), которое делает алгоритм: всегда <H*W  . ==H*W быть не может, ни когда.
//Последняя строка выравниванию не подлежит, тоже простое свойство, алгоритма:  - n количество обменов.
 
//Что бы не тратить время, свойство равнопроцентности в алгоритме не проверяеися.
//А если матрица не равнопроцентная по результату работы можно будет это понять.
 
 
/*
Алгоритм работает стабильнее и быстрее некоторых сортировок, 
совершает меньше перезаписей блоков памяти, и это вообще не сортировочный алгоритм, зачем сравнивать,
в этом я не вижу смысла, что с чем сравнивать?
    
И вообще смотреть пошагово на сортировку данных:  равно-процентных матриц мне лично не нравиться, выглядит не красиво.    
Мне приятнее, когда в каждом шаге делается кокретное, а не просто топтание на одном месте...
 
*/
 
//Основной код:
//------------------------------------------------------------------------------------------------------------------
const long H = 40;               //высота матрицы.
const long W = 40;               //ширина матрицы.
/*Массив ключей от рядов можно настроить и на другую матрицу, имеющию стандартную равнопроцентную структуру */
//Массив ключей от рядов.
const int RAD_KEYS[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40};                 //правильный ключ от каждого ряда
typedef int RAT_MATRIX[H][W];                                                 //тип матрицы.                                   
/*
 
//Пройденные тесты:
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//-------------------------------------------------------------------------------------------------------------------
(1)
 {1,4,4,4,4,4,5,7,8,8}
 {2,2,1,1,3,3,5,7,8,8}
 {2,2,2,1,1,2,5,7,9,9}
 {4,4,4,4,4,6,7,8,9,9}
 {1,1,2,2,5,6,7,8,9,10}
 {3,3,3,3,5,6,7,8,9,10}
 {5,5,5,5,5,6,7,9,10,10}
 {2,6,6,6,6,7,8,9,10,10}
 {3,3,3,3,6,7,8,9,10,10}
 {1,1,1,2,6,7,8,9,10,10}
при H == 10 (100 элементов)
    W == 10
 
swaps: 79
return:  79
const int RAD_KEYS[] = {1,2,3,4,5,6,7,8,9,10};
//--------------------------------------------------
(2)
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20}   
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20}                           
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19}                            
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20}                            
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20}                             
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20}                      
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20}                          
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20}                           
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11}                       
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11}   
                           
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11}
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11}  
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20} 
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20} 
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20} 
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20}  
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20} 
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19}  
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20} 
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20} 
 
при  H == 20  (400 элементов).
     W == 20
 
swaps: 352
return: 352
const int RAD_KEYS[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
//-------------------------------------------------------------------------
(3)
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40}                        
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                        
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                           
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                    
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}                        
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21}                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21} 
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21} 
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21} 
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40}
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40}
  
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40}
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40}                       
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                         
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                          
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                 
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}                         
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}  
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21}
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21}
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}  
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}  
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40} 
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
                              
при  H == 40  (1600 элементов).
     W == 40
swaps: 1505
return: 1505
const int RAD_KEYS[] = 
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40};
*/
 
int count = 0;
long m_print(RAT_MATRIX matrix, const int h , const int w);                   
long m_transform(RAT_MATRIX matrix, const int h , const int w);     
         
int main(){
 
    RAT_MATRIX matrix = {
 
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40},                       
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                        
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                           
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                    
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},                        
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21},                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21}, 
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}, 
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}, 
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40},
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40},
  
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40},
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40},                       
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                       
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                         
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                          
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                 
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},                         
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                         
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21},                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21},  
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21},
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21},
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},  
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40}, 
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 
};
 
m_transform(matrix,H,W); 
m_print(matrix,H,W);
 
printf("Swaps: %d",count);
system("pause");
return 0;
}
 
 
//вывод матрицы.
long m_print(RAT_MATRIX matrix, const int h , const  int w){
    for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++){
        printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
printf("\n");
return 0;
}
 
 
long m_transform(RAT_MATRIX matrix, const int h , const int w){
int i,j;
for( i = 0 ; i < h ; i++ ){
if (i == h - 1)break;    
    for( j = 0 ; j < w ; j++ ){
 
 
     if(matrix[i][j]!=RAD_KEYS[i]){
       int r = j;
       for(int k = i ; k < h; k++ ){
          for(; r < w; r++){
                    if(matrix[k][r]==RAD_KEYS[i]){                 
                    int tmp = matrix[k][r];
                    matrix[k][r]=matrix[i][j];
                    matrix[i][j] = tmp;
                    r=w; //выход.
                    k=h; //выход.
count++;
                    } // if found 
          } //;r<w
 
        r = 0;
 
     }//int k = i
 
 
}//if !=key
 
}//for( j = 0;
 
}//for( i = 0
 
 
return 0;
}

#include <stdio.h>
#include <stdlib.h>
//Показатели qsort:
/*
//Пройденные тесты:
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//-------------------------------------------------------------------------------------------------------------------
(1)
 {1,4,4,4,4,4,5,7,8,8}
 {2,2,1,1,3,3,5,7,8,8}
 {2,2,2,1,1,2,5,7,9,9}
 {4,4,4,4,4,6,7,8,9,9}
 {1,1,2,2,5,6,7,8,9,10}
 {3,3,3,3,5,6,7,8,9,10}
 {5,5,5,5,5,6,7,9,10,10}
 {2,6,6,6,6,7,8,9,10,10}
 {3,3,3,3,6,7,8,9,10,10}
 {1,1,1,2,6,7,8,9,10,10}
при H == 10 (100 элементов)
    W == 10
swaps: 229.
return: 229.
//--------------------------------------------------
(2)
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20}   
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20}                           
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19}                            
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20}                            
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20}                             
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20}                      
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20}                          
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20}                           
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11}                       
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11}   
                           
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11}
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11}  
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20} 
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20} 
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20} 
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20}  
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20} 
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19}  
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20} 
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20} 
 
при  H == 20  (400 элементов).
     W == 20
 
swaps: 1177.
return: 1177. 
//-------------------------------------------------------------------------
(3)
 
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40}                        
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                        
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                           
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                    
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}                        
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21}                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21} 
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21} 
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21} 
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40}
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40}
  
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40}
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40}                       
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                         
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                          
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                 
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}                         
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}  
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21}
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21}
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21}
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}  
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}  
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40} 
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}                            
 
при  H == 40  (1600 элементов).
     W == 40
//----------------------------------------------------------------------------------------------------------------
swaps: 5889. 
return: 5889. 
Настораживает тот факт, что стек после qsort придётся раскручивать долго и нудно, а где приеимущество?
А если обменивать обратно: большие блоки памяти, через сохранённые позиции: [i] в стеке.
И где же : ultra return ??????!!!!....
...................................................................................................................
//-----------------------------------------------------------------------------------------------------------------
*/
int count = 0 ;
const int H = 40;
const int W = 40;
typedef int RAT_MATRIX[H][W];
 
long qsort(int *mass, int size);
long m_print(RAT_MATRIX matrix, const int h , const  int w);
 
 
int main(){
int matrix[H][W] = {
 
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40},                        
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                        
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                           
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                    
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},                        
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21},                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21}, 
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}, 
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21}, 
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40},
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40},
  
 {1,4,4,4,4,4,5,7,8,8,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,35,37,38,39,40},
 {2,2,1,1,3,3,5,7,8,8,12,11,14,13,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,33,32,31,34,35,36,37,38,39,40},                       
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,20,19,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                        
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                         
 {1,1,2,2,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                          
 {3,3,3,3,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                 
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},                         
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},                          
 {3,3,3,3,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21},                     
 {1,1,1,2,6,7,8,9,10,10,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,30,40,29,28,27,26,25,24,23,22,21},  
 {1,4,4,4,4,4,5,7,8,8,20,19,18,17,16,15,14,13,12,11,31,39,38,37,36,35,34,33,32,40,30,29,28,27,26,25,24,23,22,21},
 {2,2,1,1,3,3,5,7,8,8,20,19,18,17,16,15,14,13,12,11,32,39,38,37,36,35,34,33,40,31,30,29,28,27,26,25,24,23,22,21},
 {2,2,2,1,1,2,5,7,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},
 {4,4,4,4,4,6,7,8,9,9,11,12,13,14,15,16,17,18,19,20,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21},
 {1,1,2,2,5,6,7,8,9,10,15,12,13,14,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40},  
 {3,3,3,3,5,6,7,8,9,10,11,12,13,15,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {5,5,5,5,5,6,7,9,10,10,11,12,13,14,15,16,17,19,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {2,6,6,6,6,7,8,9,10,10,11,12,13,14,15,16,17,18,20,19,22,21,24,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}, 
 {3,3,3,3,6,7,8,9,10,10,12,11,14,13,15,16,17,18,19,20,30,22,23,24,25,26,27,28,29,21,31,32,33,34,35,36,37,38,39,40}, 
 {1,1,1,2,6,7,8,9,10,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40} 
};
 
int *mas = (int*)matrix;
qsort(mas,H*W);
m_print(matrix,H,W);
printf("Swaps: %d",count);
printf("\n");
 
 
system("pause");
return 0;
}
 
 
long qsort(int *mass, int size){    
int i = 0, j = size;   
int temp, p;
      p = mass[ size>>1 ];     
     
     do {
        while (mass[i] < p) i++;
        while (mass[j] > p) j--;
 
    if (i <= j) {
      count++;
      temp = mass[i];
      mass[i] = mass[j]; 
      mass[j] = temp;
      i++; j--;
    }
} while (i <= j);
     
if ( j > 0 ) qsort(mass, j);
if ( size > i ) qsort(mass+i, size-i);
return 0;
}
 
 
//вывод матрицы.
long m_print(RAT_MATRIX matrix, const int h , const  int w){
    for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++){
        printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
  printf("\n");
return 0;
}