Сортировка матрицы

← →
исследователь (2007-04-28 18:51) [0]

Здравствуйте, уважаемые!
Есть задача: отсортировать заданную матрицу 5 на 5, переместив в ней строки по возрастанию элементов главной диагонали.
Задача, вроде бы, и не сложная, но в процессе решения натолкнулся на следующие проблемы:

1) как запомнить порядок,в котором должны быть все строки? Использовать массив? Ведь если менять строки местами в порядке прогона i от 1 до 5,то элемент на главной диагонали в следующей итерации будет уже другим? То есть:

A:array [1..5,1..5] of Real;

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

что должно выйти после преобразования?

2) реализовать все это изящнее и с минимумом затрат памяти (посему мне вариант с доп. массивом и не нравится так).

Если можете, приведите алгоритм, или лучше - фрагмент кода. Заранее благодарен!

← →
oldman © (2007-04-28 19:41) [1]

> Есть задача: отсортировать заданную матрицу 5 на 5, переместив
> в ней строки по возрастанию элементов главной диагонали.
>

Точно таже задача, что и по сортировке матрица 5 на 1 по возрастанию...

← →
Алхимик © (2007-04-28 19:42) [2]

procedure TForm1.Button1Click(Sender: TObject); const N = 5; var A: array[1..N, 1..N + 1] of byte; tmp: array[1..N + 1] of byte; i, j: byte; str: string; begin memo1.Lines.Add("До сортировки:"); for i := 1 to n do begin str := ""; for j := 1 to n do begin A[i, j] := random(10); str := str + IntToStr(A[i, j]) + " "; end; A[i, n + 1] := A[i, i]; memo1.Lines.Add(str + " ->" + IntToStr(A[i, n + 1])); end; i := 1; repeat if A[i, n + 1] > A[i + 1, n + 1] then begin for j := 1 to n + 1 do begin tmp[j] := a[i, j]; a[i, j] := a[i + 1, j]; a[i + 1, j] := tmp[j]; end; i := 1; end else inc(i); until i = N; memo1.Lines.Add("После сортировки:"); for i := 1 to n do begin str := ""; for j := 1 to n do begin str := str + IntToStr(A[i, j]) + " "; end; memo1.Lines.Add(str + " ->" + IntToStr(A[i, n + 1])); end; end;

← →
Алхимик © (2007-04-28 19:43) [3]

> [1] oldman © (28.04.07 19:41)
>
> > Есть задача: отсортировать заданную матрицу 5 на 5, переместив
>
> > в ней строки по возрастанию элементов главной диагонали.
> >
>
>
> Точно таже задача, что и по сортировке матрица 5 на 1 по
> возрастанию...

авотфиг! :)

← →
oldman © (2007-04-28 19:45) [4]

> 1 2 3 4 5
> 6 0 7 8 2
> 4 3 8 6 9
> 5 2 4 3 5
> 9 2 5 6 1
>
> что должно выйти после преобразования?

Должно выйти:

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

Знаки вопроса означают, что на главной диагонали две единицы :(((

← →
oldman © (2007-04-28 19:46) [5]

> Алхимик © (28.04.07 19:43) [3]
> авотфиг! :)

дошло!!!

← →
oldman © (2007-04-28 19:48) [6]

> исследователь (28.04.07 18:51)

У тебя во второй строке 0 все портит :)))

← →
palva © (2007-04-28 19:48) [7]

По-моему, без дополнительного вектора не обойтись. Или проще, дополните матрицу еще одним столбцом, куда в самом начале алгоритма перенесите диагональные элементы.

На самом деле вы не должны бояться расходования дополнительной памяти. Если матрица очень большая, то на перестановку строк будет уходить довольно много времени. Особенно если будете применять метод пузырька. Так что экономнее будет завести матрицу из двух столбцов, в первый столбец занести номера строк (1,2,3...) а во второй диагональный элемент. Такую матрицу можно быстро отсортировать, а затем переместить строки исходной матрицы. Здесь требуется кропотливое программирование, но программа будет работать быстро.

← →
oldman © (2007-04-28 19:50) [8]

Поскольку, (имхо) после перестановки главная диагональ должна быть возрастающей.
А первого элемента меньше нуля нет :(((

← →
Алхимик © (2007-04-28 19:57) [9]

> [8] oldman © (28.04.07 19:50)
> Поскольку, (имхо) после перестановки главная диагональ должна
> быть возрастающей.
> А первого элемента меньше нуля нет :(((

Нет, главная диагональ проверяется в начале.
после сортировки матрицы, новая главная диагональ не будет отсортирована
До сортировки:
0 0 8 2 2 ->0
6 3 1 3 4 ->3
0 4 0 8 0 ->0
2 9 3 7 3 ->7
6 8 7 3 1 ->1
После сортировки:
0 0 8 2 2 ->0
0 4 0 8 0 ->0
6 8 7 3 1 ->1
6 3 1 3 4 ->3
2 9 3 7 3 ->7

← →
oldman © (2007-04-28 19:59) [10]

> Алхимик © (28.04.07 19:57) [9]

Тогда возникает другая пробдлема:
до сортировки в гланой диагонали равные элементы!

← →
Алхимик © (2007-04-28 20:02) [11]

> [10] oldman © (28.04.07 19:59)
>
> > Алхимик © (28.04.07 19:57) [9]
>
>
> Тогда возникает другая пробдлема:
> до сортировки в гланой диагонали равные элементы!

Ну это уже от задачи зависит.
p.s. Представилось построение на уроке физкультуры по росту... Физрук завис на двух близнецах. :)

← →
default © (2007-04-28 20:27) [12]

[7] дело говорит

← →
исследователь (2007-04-28 21:01) [13]

Я покорнейше прошу прощения, но не могли бы вы прокомментирвоать следующий фрагмент:

i := 1; repeat if A[i, n + 1] > A[i + 1, n + 1] then begin for j := 1 to n + 1 do begin tmp[j] := a[i, j]; a[i, j] := a[i + 1, j]; a[i + 1, j] := tmp[j]; end; i := 1; end else inc(i); until i = N;

В n+1-ом столбеце содержатся, судя по всему, текущий элемент главной диагонали. Затем вы сравниваете элемент в двух соседних строках, и, если первый сверху больше второго, то строки меняются местами. Но почему затем i:=1 ? Получается, опять идет прогон? Зачем это сделано?

← →
default © (2007-04-28 21:08) [14]

прочти что palva написал
там на словах все объяснено, а не в коде
решение Алхимика в общем случае плохо потому что алгоритм сортировки медленный и перемещаются строки, хотя можно быстрее как объяснил palva работая с матрицей диагональных элементов и номеров строк

← →
default © (2007-04-28 21:09) [15]

исследователь (28.04.07 21:01) [13]
это обычный метод пузырька:)

← →
исследователь (2007-04-28 21:17) [16]

По сути, предлагается palva, чтобы я получил вначале матрицу

X[1..5,1..2] of real

1 8 2 3 3 6 4 2 5 1, затем пробег по i от 1 до 4,
по j от i+1 до 5,
если X[i,2]>x[j,2], то меняем строки в матрице Х местами, а заметь анализируем эту матрицу, выбираем из первого столбца номера строк и меняем их в матрице А, я верно понял?

← →
default © (2007-04-28 21:26) [17]

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

-->

1 1
2 0
3 8
4 3
5 1

сортируем это матрицу по второму столбцу каким-либо методом и получаем,
например,
2 0 (то есть строка номер 2 должна стать первой)
1 1
5 1 (строка номер пять должна стать третьей)
4 3
3 8

и потом по этой таблице соответсвующим образом меняем строки в исходной матрице

← →
исследователь (2007-04-28 22:05) [18]

То ли у меня уже совсем мозг плавится, но вот это:

for i:=1 to 5 do begin k := x[i,1]; kk:=i; writeln; writeln("Меняю строки ",k," и ",kk); for j:= 1 to 5 do begin temp:=a[kk,j]; a[kk,j]:=a[k,j]; a[k,j]:=temp; write(a[kk,j]," "); end; end;

не работает...в чем трабл?

← →
исследователь (2007-04-28 22:54) [19]

Я понял ошибку, но не знаю, как переписать. Строки при подборе идут так:

for i:=1 to 5 do begin k := x[i,1]; kk:=i; writeln; writeln("Меняю строки ",k," и ",kk); for j:= 1 to 5 do begin temp:=a[kk,j]; a[kk,j]:=a[k,j]; a[k,j]:=temp; write(a[kk,j]," "); end; end;

при этом строка, скажем, первая может быть изменена дважды и т.д.

← →
исследователь (2007-04-28 23:44) [20]

черт, помогите с алгоритмом перемещения строчек!!!

← →
default © (2007-04-29 00:14) [21]

пожалуй, тебе стоит остановиться на варианте Алхимик © (28.04.07 19:42) [2]
он вполне нормальный если смотреть на матрицу 5x5 как в условии у тебя указано
если ты сходу метод пузырька не увидел значит пока рано, хотя сложно вообще ничего нет...просто ты модульно мысли...выдели подпрограммы отвечающую, например, за получение матрицы которую сортируем из исходной матрицы, потом подпрограмму сортировки этой матрицы, потом подпрограмму корректировки исходной матрицы по отсортированной матрицы
и каждую подпрограмму отлаживай после написания, отлаживать меньшие куски как правио проще чем более крупные

← →
default © (2007-04-29 00:16) [22]

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

← →
исследователь (2007-04-29 00:18) [23]

Понимаешь, default, я не могу написать именно часть, где КОРРЕКТИРУЕТСЯ ИСХОДНАЯ МАТРИЦА ПО ОТСОРТИРОВАННОЙ. Помоги, пожалуйста!

← →
default © (2007-04-29 00:26) [24]

исследователь (29.04.07 00:18) [23]
если у тебя задача с матрицей 5x5 используй варианта Алхимика, усложнять тут не стоит(используя подход palva)
ты понял идею и хорошо

← →
исследователь (2007-04-29 00:30) [25]

Меня достает один вопрос этот, он уже мучает меня. Смотри, я отсортировал вспомогат. массив. Как теперь пройтись по его элементам, чтобы поменять местами элементы матрицы?

переместить-то не проблема, только в голову лезут квадритичные варианты, что собъёт сложность O(nlog(n)) хорошей сортировки
можно держать две матрицы
1 1
2 0
3 8
4 3
5 1
и его отстортированную версию
2 0 (то есть строка номер 2 должна стать первой)
1 1
5 1 (строка номер пять должна стать третьей)
4 3
3 8
тогда корректировку можно сделать быстро довольно(не сбиваясь на общую квадритичную сложность всего алгоритма)
подумай как, я спать уже иду(если что сегодня днём опишу)
может кто другой лучше предложит сделать корректировку

← →
исследователь (2007-04-29 01:13) [27]

тогда можно уже сделать через введение доп. массива 5 на 5 =)

я тоже спать, надо будет еще на эту темы поговорить. Пост НЕ закрываем. если что, моя аська 863927.

> [13] исследователь (28.04.07 21:01)
> Я покорнейше прошу прощения, но не могли бы вы прокомментирвоать
> следующий фрагмент:
...

> Но почему затем i:=1 ? Получается, опять идет прогон? Зачем
> это сделано?

Сортировка. Метода называется "Пузырёк".
Как правильно заметили предыдущие ораторы, моя метода в общем виде плоха тем, что в процессе сортировки меняются местами строки матрицы.

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

← →
исследователь (2007-04-29 14:05) [30]

> vovnuke

я именно так в конце концов и сделал

> [30] исследователь (29.04.07 14:05)
>
> > vovnuke
>
> я именно так в конце концов и сделал

А чем [2] не вдохновило?

можно ещё попробовать поработать с одномерным массивов элементами которого являются одномерные динамические массивы и тогда можно перемещать указатели на строки матрицы(элементы массива), а не целые строки, размерность динамических массивов можно сделать N+1 и записать в последний элемент соответсвующее диагональное значение чтобы иметь возможность по указателям строк матрицы выполнять сравнение

← →
исследователь (2007-04-30 13:50) [33]

вдохновило... И. кстати:

что вводи доп. матрицу - расход памяти

что делай по-твоему - расход времени

что особенно заметно на матрицах, скажем, 100 на 100 и более

Где компромисс?

> [33] исследователь (30.04.07 13:50)
> Где компромисс?

в постановке задачи

Сортировка матрицы Найти похожие ветки