Сортировка выше побочной диагонали

[pasha18]

Помогите пожалуста решить задачу на Паскале!

Дана матрица M x N.
Отсортировать по возрастанию элементы стоящие выше побочной диагонали.(элементы вводятся с клавиатуры)

[Serge_Bliznykov]

1) задача имеет решение ТОЛЬКО при M == N
т.к. только для квадратных матрицы существуют определения главной и побочной диагонали.

2) невозможно запрограммировать то, что Вы не понимаете..

Отсортировать по возрастанию

отсортировать КАК?!

допустим, есть матрица 5x5

6 2 7 3 1
7 8 9 1 0
5 4 1 0 0
3 1 0 0 0
1 0 0 0 0

приведите пример отсортированной матрицы...

[red-white]

да вроде матрица не обезательно должна быть квадратной, по крайней мере мне препод так сказал)

вот так она должна отсортироваться
2 3 3 4 1
5 6 7 1 0
7 8 1 0 0
9 1 0 0 0
1 0 0 0 0

[dasvex]

хм насчет паскаля не знаю . но вот быстренько набросал на с++ код
получилось слегка громоздко ))

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main ()
{
short m=5;
short n=5;

short **p=new short *[n];                                //
for(short i=0;i<n;i++){	p[i]=new short [m]; }       //создаем массив м*н 

for(short i=0;i<n;i++)
{
	for(short j=0;j<m;j++)
	{
		cout<<"p["<<i<<"]["<<j<<"]"<<endl;
		cin>>p[i][j];
	}
}
	
cout<<"ur matrix:\n";
for(short i=0;i<n;i++) //этот цикл будет отображать твою матрицу
{
	for(short j=0;j<m;j++)
	{
		cout <<"  ["<< p[i][j]<<"]  ";
		if (j==n-1)cout<<"\n";
	}
}
//а вот сама сортировка

bool flag=true;
while(flag)
{	
	flag=false;
	for(short i=0;i<n;i++)
	{
		for(short j=0;j<m;j++)
		{
			if(i+j>=m-1) continue; // если выше побочной диагонали значит сумма индексов
                                                      //должна быть меньше m-1 . что и и выражает данное условие 
			if(i+j+1==m-1)          // для сравнения элементов разных строк
			{
				if(p[i][j]>p[i+1][0])  //сама перестановка
				{
					short tmp=p[i][j];
					p[i][j]=p[i+1][0];
					p[i+1][0]=tmp;	
					flag=true;	
					continue;
				}	
			}
			if(p[i][j]>p[i][j+1])  //сама перестановка
			{
				short tmp=p[i][j];
				p[i][j]=p[i][j+1];
				p[i][j+1]=tmp;
				flag=true;			
			}
		}
	}
}


//отображаем опять твою матрицу , уже отсортированную 	
cout<<"ur matrix:\n";
for(short i=0;i<n;i++)
{
	for(short j=0;j<m;j++)
	{
		cout <<"  ["<< p[i][j]<<"]  ";
		if (j==n-1)cout<<"\n";
	}
}

//удаляем выделеную память 
for(short i=0;i<m;i++)	delete[] p[i];	
delete[] p;

system("pause");
return 0;
}

блин с меня обьясняла никакой )
както так.должно работать
и ах да . будет работать только с квадратной ) ибо про диагональ не квадратной матрицы ничего не знаю )

[Serge_Bliznykov]

да вроде матрица не обезательно должна быть квадратной, по крайней мере мне препод так сказал)

Или Вы его не поняли, или он ошибается.
Или у него собственные представления о побочной диагонали...
Попробуйте нарисовать ему матрицу, например, 3x7 и попросить его отметить элементы, состовляющие побочную диагональ (если у него получится, то пусть проделает то же самое, например, с матрицей 2x10)

по поводу решения.
я бы предложил такой вариант.
он не самый оптимальный - зато самый простой в реализации.
объявить дополнительный одинарный массив размером (N^2 - N) div 2
простым циклом перебросить туда элементы, находящиеся выше побочной диагонали.
отсортировать этот массив.
Перебросить элементы из одномерного массива обратно на свои места в матрицу.

const N = 5;
var
  M : array[1..N, 1..N] of integer;
  B : array[1..(N*N-N) div 2] of integer;
  tmp_element  : integer;
  {переменные для индексов}
  i, j, k, IndexMin : integer;
begin
  { ввод массива }
  for i:=1 to N do
    for j:=1 to N do begin
      Write('M[',i,',',j,'] =');
      Readln(M[i,j]);
    end;

  {переброс эл.выше побочной диагонали
     в одномерный массив}
  k:=0;
  for i:=1 to N do
    for j:=1 to N do
      {элемент выше главной диагонали?}
      if i<(N-j+1) then begin
        inc(k);
        B[k] := M[i,j];
      end;

  WriteLn('Для отладки выведем содержимое массива B (до сортировки):');
  for i:=1 to K do
    Write(B[i]:4);
  Writeln;

  {сортировка массива B}
  for i:=1 to k-1 do begin
    IndexMin := i;
    for j:=i+1 to k do
      if B[j]<B[IndexMin] then IndexMin := j;
    if i<>IndexMin then begin
      tmp_element := B[i];
      B[i] := B[IndexMin];
      B[IndexMin] := tmp_element;
    end;
  end;

  WriteLn('Для отладки выведем содержимое массива B (после сортировки):');
  for i:=1 to K do
    Write(B[i]:4);
  Writeln;


  {перебросим элементы из массива B
    обратно в матрицу}
  {переброс эл.выше побочной диагонали
     в одномерный массив}
  k:=0;
  for i:=1 to N do
    for j:=1 to N do
      {элемент выше главной диагонали?}
      if i<(N-j+1) then begin
        inc(k);
        M[i,j] := B[k];
      end;


  {вывод результата}
  WriteLn;
  WriteLn('Матрица с отсортированными элементами выше побочной диагонали:');
  for i:=1 to N do begin
    for j:=1 to N do
      Write(M[i,j]:4);
    WriteLn;
  end;

  Readln;
end.

безусловно и в данном алгоритме можно сделать качественные улучшения...
Да и можно написать сортировку "на месте" - прямо в матрице...

[red-white]

Спасибо, вроде работает