(ст)Сортировка двумерного массива, пользуясь суммой элементов.

[be3]

Дана матрица А размером 20x20. Считая ее составленной из 100 квадратов размером 2х2 и переставляя эти квадраты преобразовать А так, что бы в результирующей матрице для всяких двух квадратов B и C выполнялось следующее условие: если сумму элементов B, меньше суммы элементов С, то B лежит либо выше, либо левее (когда B и C на одной горизонтали) квадрата С.

Проблема состоит в написании и собственно в разработке алгоритма. Т.е. если бы условие было сортировать не всю матрицу по возрастанию, а допустим по столбцам все было бы гораздо проще.

Вот код который имею на данный момент...

Код:

...

Мне предложили некоторое решение моей задачки, но к сожалению оно так и осталось непонятным. Может у кого будут некоторые соображения по этому поводу.


Задача берётся влоб.
Заметим, что если получилась какая-то матрица, удовлетворяющая требуемым условиям, то транспонированная к ней тоже будет удовлетворять этим условиям, поэтому как сортировать - не важно. Итак, едем...

Код:

...

[be3]

Решение готово

Код:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
const int n=6;
typedef int Matrix[n][n];
/*ввод матрици с клавиатуры*/
void EnterMatrix(Matrix Matr){
for(int i=0; i<n; i++){
	for (int j=0; j<n; j++){
   	printf("Matr[%d,%d]",i,j);
      scanf("%d", &Matr[i][j]);
      }}}

/*Генерация эелементов матрицы*/
void GenerateMatrix(Matrix Matr){
int max, min;
printf("Vvedite diapozon zna4eniy\n max=");
scanf("%d", &max);
printf("\n min=");
scanf("%d", &min);
for (int i=0; i<n; i++)
	for (int j=0; j<n; j++)
   Matr[i][j]=random(max-min)+min;
   }
/*Вывод матрицы*/
void PrintMatrix(Matrix Matr){
for (int i=0; i<n; i++){
	for( int j=0; j<n; j++){
      printf ("%d ", Matr[i][j]);
      }
      printf ("\n");
      }};

int sum(Matrix &Matr, int pos) {
int row = pos / (n / 2);
int column = pos % (n / 2);
row *= 2;
column *= 2;
int sum=Matr[row][column]+Matr[row][column+1]+Matr[row+1][column]+Matr[row+1][column+1];
return sum;
}
void swap(Matrix &Matr, int i, int j, int k, int z) {
int a = Matr[i][j];
Matr[i][j] = Matr[k][z];
Matr[k][z] = a;
}
void swap(Matrix &Matr, int pos1, int pos2) {
int row1 = pos1 / (n / 2);
int column1 = pos1 % (n / 2);
int row2 = pos2 / (n / 2);
int column2 = pos2 % (n / 2);
row1 *= 2;
column1 *= 2;
row2 *= 2;
column2 *= 2;
swap(Matr, row1, column1, row2, column2);
swap(Matr, row1, column1 + 1, row2, column2 + 1);
swap(Matr, row1 + 1, column1, row2 + 1, column2);
swap(Matr, row1 + 1, column1 + 1, row2 + 1, column2 + 1);
}
/*Сортировка матрицы по условию задачи*/
void Sortirovka(Matrix &Matr){
int sum1, sum2;
char is=1;
int i;
int len = (n * n) / 4 ;
 while(is)
 {
is=0;
for (i=1; i<len; i++) {
sum1 = sum(Matr, i);
sum2 = sum(Matr, i - 1);
if ( sum1 < sum2 )
{
swap(Matr, i, i - 1);
is=1;
}
}
 }
}


main(){
int dey=0;
Matrix M;
char ask;

do{
/*Выбор действия*/
printf("Viberite neobhodimoe deystvie i najmite ukazannuu klavi6u\n");
printf ("(a)Vvesti matricu s klaviaturi\n");
printf ("(b)Sgenirirovat' matricu\n");
printf ("(c)Vivesti matricu na ekran\n");
printf ("(d)Sortirovka\n");
printf ("(e)Exit\n");
scanf("%c", &ask);
switch(ask){
case 'a':{
printf("Vvod matrici s klaviaturi\n");
EnterMatrix(M);
printf ("Polu4ivwaysja matrica\n");
PrintMatrix(M);
dey=1;
getch();
break;
};
case 'b':{
printf ("Generacija matrici\n");
GenerateMatrix(M);
printf ("Polu4ivwaysja matrica\n");
PrintMatrix(M);
dey=1;
getch();
break;
};
case 'c':{
if (dey==1){
printf ("Vivod matrici\n");
PrintMatrix(M);
} else break;
getch();
break;
};
case 'd':{
if (dey==1){
printf ("Sortirovka po usloviu zada4i\n");
Sortirovka(M);
PrintMatrix(M);
} else break;
getch();
break;
};
};
} while (ask!='e');
}

[Finch]

В третьем томе книги Д.Кнута "Искуство программирования" описывается помоему 32 алгоритма сортировки массивов. Выбирай на любой вкус. Самый быстрый для данных хранимых в памяти компьютера считается алгоритм побитовой сортировки. Количество полных проходов в нем зависит от разрядности сортируемых данных. Алгоритм имеет большой минус. Нужно его настраивать на сортируемые данные. Второй по быстроте алгоритм "Quick Sort". Этот алгоритм довольно часто встречается в реализациях библиотек. смысл такой: Берется элемент массива и выгоняется на свое место в массиве. т.е. если массив сортируется по возрастаюшей, то элементы меньше по индексу будут меньше контрольного элемента. Выше по индексу будут больше контрольного элемента. Дальше массив разбивается на две части. Первая часть те элементы которые меньше контрольного элемента. Вторая часть те элементы которые больше контрольного элемента. Производится сортировка уже этих частей по тому же алгоритму.

[Алексей++]

(комент)

статья по алгоритмам сортировки?