Сортировка 2D массива змейкой, Отсортировать массив как показано на схеме Опции

[MC-Sergey]

Данн двумерный массив n на m, состоящий из любых целых чисел.
Необходимо отсортировать массив змейкой по возрастанию(убыванию), как показано на рисунке.
Задавать дополнительный массив запрещено.
Голову уже сломал себе

Сообщение отредактировано: MC-Sergey - 21.10.2007 17:50

[klem4]

решалось ... попробуй найти в поиске, сам не пробовал сделать ?

[MC-Sergey]

решалось ... попробуй найти в поиске, сам не пробовал сделать ?

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

Сообщение отредактировано: MC-Sergey - 21.10.2007 18:42

[мисс_граффити]

То что нашлось поиском, примитивные задачи по сортировке строками и столбцами только в разных направлениях.

а эта задача - что-то другое? не сортировка "в разных направлениях"???

[MC-Sergey]

а эта задача - что-то другое? не сортировка "в разных направлениях"???

тут по диагонали.
Если не понятно с картинки, вот в цифрах чтобы было понятнее(напрвление сортировки):
01 02 06 07 14 15
03 05 08 13 16 21
04 09 12 17 20 22
10 11 18 19 23 24

Если можно, в кратце как работает алгоритм и код программы(если есть; в Паскале)
Вся надежда на вас, у меня на этот момент идеи закончились свои...

Сообщение отредактировано: MC-Sergey - 21.10.2007 19:42

[мисс_граффити]

запиши все диагонали в индексах.
и посмотри, нет ли закономерности... как изменяется i, как изменяется j

[MC-Sergey]

Матрица, по-моему, может быть только квадратной.

вот в этом то и проблема. мне известно что данная задаче рашается, и что определенный алгоритм решения работает как для квадратной матрицы, так и для любой другой.
Если у кого то будут еще идеи по решению данной задачи, пожалуйста пишите.
даже если это просто ваши мысли "вслух".
Мне интересно, почему еще не заинтересовались люди, которые "мозг" этого форума. Задача на мой взгляд очень интересная (в смысле сложности написания кода).

[klem4]

uses crt;

const
  n = 5;
  m = 3;

type
  TArray = array [1..n, 1..m] of Integer;

procedure Print(const arr: TArray);
var
  i, j: integer;
begin
  for i := 1 to n do begin
    writeln;
    for j := 1 to m do begin
      write(arr[i, j]:4);
    end;
  end;
end;

procedure Create(var arr: TArray);
var
  i, j, value: integer;
begin

   value := 1;

   i := 1;
   j := 1;

   arr[i, j] := value;

   repeat

     if j < m then begin
       inc(j);
       inc(value);
       arr[i, j] := value;
     end else begin
       inc(i);
       inc(value);
       arr[i, j] := value;
     end;

     while (j > 1) and (i < n) do begin
       dec(j);
       inc(i);
       inc(value);
       arr[i, j] := value;
     end;

     if i < n then begin
       inc(i);
       inc(value);
       arr[i, j] := value;
     end else if j < m then begin
       inc(j);
       inc(value);
       arr[i, j] := value;
     end;

     while (i > 1) and (j < m) do begin
       dec(i);
       inc(j);
       inc(value);
       arr[i, j] := value;
     end;

   until (i = n) and (j = m);
end;

var
  arr: TArray;
begin
  clrscr;
  Create(arr);
  Print(arr);
  readln;
end.

[volvo]

В смысле сложности написания - это порядка 80 строк, вместе с выводом результатов... Ты лучше скажи, что значит "сортировать"? То есть, у тебя есть массив, заполненный какими-то данными, и ты должен его отсортировать так, чтобы пройдя по тому пути, что ты нарисовал, ты получил бы упорядоченные по возрастанию/убыванию элементы массива?

[MC-Sergey]

В смысле сложности написания - это порядка 80 строк, вместе с выводом результатов... Ты лучше скажи, что значит "сортировать"? То есть, у тебя есть массив, заполненный какими-то данными, и ты должен его отсортировать так, чтобы пройдя по тому пути, что ты нарисовал, ты получил бы упорядоченные по возрастанию/убыванию элементы массива?

Да ты прав... Я вроде написал об этом в задании (см. первый пост).

По твоему решению:
klem4, а вот и не так...
Массив задается рандомом (или вручную - не важно) и уже потом сортируется, как ты сказал ранее.

Сообщение отредактировано: MC-Sergey - 21.10.2007 21:34

[klem4]

Массив задается рандомом (или вручную - не важно)

а я по твоему телепат ?!

а вот и не так...

ну сделай "так" и покажи нам. Я больше ни строки не напишу.

[volvo]

Ну, сортировка - так сортировка

const
  max_col = 6;
  max_row = 4;

type
  tdirection = (right, left_down, down, right_up);
const
  delta: array[tdirection] of record X, Y: integer end =
  ( (X: 1; Y: 0), (X:-1; Y: 1), (X: 0; Y: 1), (X: 1; Y:-1) );

function get_next(var dir: tdirection; var col, row: integer): boolean;
var
  new_col, new_row: integer;
  ok: boolean;
begin
  get_next := false;
  if (row = max_row) and (col = max_col) then exit;

  case dir of
    right:
      if row = 1 then dir := left_down
      else dir := right_up;
    down:
      if col = 1 then dir := right_up
      else dir := left_down;
  end;

  repeat

    new_col := col + delta[dir].x; new_row := row + delta[dir].y;
    ok := (new_col >= 1) and (new_col <= max_col) and
          (new_row >= 1) and (new_row <= max_row);

    if not ok then
      case dir of
        right: dir := down;
        left_down: dir := down;
        down: dir := right;
        right_up: dir := right;
      end;

  until ok;
  col := new_col; row := new_row;
  get_next := true;

end;

var
  a: array[1 .. max_row, 1 .. max_col] of integer;
  dir: tdirection;

  i, j,
  _col, _row,
  first_row, first_col, mx_row, mx_col: integer;
  value: integer;
  T: integer;

begin
  for _row := 1 to max_row do
    for _col := 1 to max_col do
      a[_row, _col] := random(20);

  for i := 1 to max_row * max_col - 1 do begin

    _col := 1; _row := 1;
    dir := right_up;

    for j := 1 to pred(i) do get_next(dir, _col, _row);
    first_col := _col; first_row := _row;

    mx_row := first_row; mx_col := first_col;
    repeat

      if a[mx_row, mx_col] > a[_row, _col] then begin
        mx_row := _row; mx_col := _col;
      end

    until not get_next(dir, _col, _row);
    T := a[first_row, first_col];
    a[first_row, first_col] := a[mx_row, mx_col];
    a[mx_row, mx_col] := T;

  end;

  for _row := 1 to max_row do begin
    for _col := 1 to max_col do begin
      write(a[_row, _col]:4);
    end;
    writeln;
  end;

end.

Попробуй разобраться...

[MC-Sergey]

volvo дааа... ну ты и голова!
А более простого рещения точно нет?
Пытаюсь разобраться, пока с трудом...
Не можешь в кратце изложить как программа работает. А то я путаюсь в твоих тщательно продуманных лабиринтах.

Как то бы вот это заменить

const
  delta: array[tdirection] of record X, Y: integer end =
  ( (X: 1; Y: 0), (X:-1; Y: 1), (X: 0; Y: 1), (X: 1; Y:-1) );

Я это не понимаю.

Сообщение отредактировано: MC-Sergey - 22.10.2007 2:08