Сортировка двумерного массива

[burik]

Предстоит сделать лабораторную. В общем вот что написано в задании:

Необходимо разработать библиотеку подпрограмм, записать алгоритмы всех
подпрограмм в виде блок-схемы и реализовать их на языке C. Кроме
операций перечисленных в задании необходимо разработать и реализовать
операцию вывода данных на экран и тестовую программу, которая
обеспечивает функциональное тестирование разработанной библиотеки.

Далее мой вариант задания:

3. Двухмерный массив. Сортировка массива. Вставка элемента в
отсортированный массив. Поиск элемента в отсортированном массиве.
Объединение двух отсортированных массивов. Пересечение двух
отсортированных массивов.

У меня возникло некоторое замешательство по части сортировки массива и вставки в него элемента.
Может есть какие-то общепринятые нормы сортировки двумерных массивов. Т.е. как правильнее его сортировать:
по строкам, по столбцам, последовательно слева направо сверху вниз, или спиралью, наконец ?

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

[Proxy]

Мб в задании не имелось ввиду Сортировка двухмерного массива? Там точка стоит.
Самое очевидное на мой взгляд - сортировать, представляя каждый элемент двухмерного массива как элемент одномерного (т.е. индекс будет iy*w + ix, где ix, iy -- позиция по столбцу и строке двумернго, а w - горизонтальная размерность массива), т.к. иначе противоречия возникают.
Как вставить элемент в двухмерный массив без добавления элементов с неопределёнными значениями вообще не могу себе представить.
Что-то тут явно не так.

[alibek]

Что ты подразумеваешь под двухмерным массивом?
И если подразумеваешь матрицу, то что тогда подразумеваешь под вставкой элемента в массив?

[MIT]

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

[Proxy]

Странно что нет оговорок. Я вот могу представить себе таблицу как массив столбцов, которые в свою очередь содержат ячейки, образуя тем самым строки. Разве есть общепринятое понмание таблицы? Если да, тоя его упустил.

[Александр Дмитриев]

Скорее всего, имелось в виду сортировка одномерного массива и вставка элемента в одномерный массив. У индексов двумерного массива порядок лишь частичный, поэтому сортировка возможна лишь топологическая. Ну даже если его отсортировать каким-нибудь образом, то получится-то после сортировки одномерный массив. И соответственно, когда далее в задании говорится "отсортированный массив", имеется в виду одномерный массив. Но с другой стороны не понятно: какие тогда операции подразумеваются под фразой "двумерный массив"?

[burik]

В задании необходимо сортировать именно двухмерный массив. И вставлять элемент именно в двухмерный массив. Лабораторная по структурам данных. В каждом варианте задание дается определенная структура данных и операции которые моя библиотека должна позволять производить с данной структурой.

С сортировкой более-менее определился - сделал различные варианты (по строкам, по столбцам, последовательно - как Proxy предлагал, еще спилью по часовой и против). Но вот с добавлением элемента пока не знаю как быть.

[Александр Дмитриев]

Тогда нужно выяснять у преподавателя, какую сортировку он имел в виду, так как отсортировать можно несколькими способами, и везде получится разный результат. Вставка элемента в отсортированный массив - это наверно построение нового массива, который имеет все элементы старого, а также новый элемент, и при этом является отсортированным. При этом опять возникает неопределённость: если нужно, например, в отсортированный массив 5x3 вставить новый элемент, то конечный массив должен иметь 15 + 1 = 16 элементов, но не понятно, будет ли он 16x1, 8x2, 4x4, 2x8 или 1x16. В общем, все эти вопросы нужно задавать преподавателю.

[Xcode]

Какая разница в каком виде массив? Помоему ты споткнулся на ровном месте.

[burik]

Какая разница в каком виде массив? Помоему ты споткнулся на ровном месте.

Разница большая.

Вот, например, надо вставить элемент 13 в одномерный отсортированный массив: {2, 4, 5, 9, 17, 43}
Результат получается однозначно такой: {2, 4, 5, 9, 13, 17, 43}

Теперь возьмем двухмерный массив. Вставим элемент 13 в массив:


Если по-твоему нет разницы, то напиши результирующий двухмерный массив.

[Andrey Fedorov]

Может есть какие-то общепринятые нормы сортировки двумерных массивов. Т.е. как правильнее его сортировать:
по строкам, по столбцам, последовательно слева направо сверху вниз, или спиралью, наконец ?

Спиралью в косую полосочку, конечно

Вообще, скорей всего, имелась в виду сортировка по одной из размерностей массива. Ну и под вставкой скорее подразумевалась вставка строки значений (в данном случае двух). Хотя, конечно, можно и уточнить у препода его понимание задачи...

[Денис]

Есть мнение, что препод, о котором речь, не понял бы половины из того, о чем здесь говорилось

[Хакер]

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

[burik]

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

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

[Хакер]

не отсортируешь таким образом.