Подскажите пожалуйста, как!? Есть задание:
отсортировать матрицу по спирали
1 8 7
2 9 6    но это не самое страшное, я придумаю, 
3 4 5    еслибы начальная матрица была отсортирована по порядку.

Есть ограничение по памяти(я не могу никак понять,что имеется ввиду! может кто сталкивался): матрица N*N, N=1000 и вся мтрица в память не помещается....

Что значит не помещается в память и как тогда ее сортировать???

я сперва хотел сортировать построчно(как одномерные массивы пр 1000 элементов)
и в функцию сортировки передавать 2 массива по 1000, сортирвать между собой, потом 2 оую и 3 строки, их отсортировать, но так не получится, потому что не ясен критерий остановки сортировки (явно не 1 проход от 0...N)


Подскажите, может есть какие методы???

вот мое предложение.
1. делаешь из матрицы одномерный массив ( в файл)
2. разбиваешь его на n частей (по m в каждой) и сортируешь
3. переставляешь части между собой (если возможно). 
4. начинаешь с m/2-ого номера и снова разбиваешь на n частей и сортируешь каждую,
сдвигаешь на -m/2 обратно и снова разбиваешь и сортируешь, и так далее.
а вообще 1000*1000 это 4 метра памяти, сэр. почему не поместится??

другой вариант - работай с массивом на винте. позиционируй каретку туда-сюда и читай-пиши цифры.

Это сообщение отредактировал(а) comcon1 - 11.10.2007, 01:24

тогда наверно вступает в действие ограничение по памяти человека - к моменту завершения выполнения программы, человек, её запустившый, забудет зачем он это сделал

сталкивался c чем-то подобным, когда просчитывал дипломную работу на XT и когда писал редактор под ДОС.
сейчас подобное может быть при навороченных расчетах.

придется юзать файл. выделяешь два буфера под размер строки  массива, в которые будешь читать строки массива из файла. (под это дело придется прописать две функции, одна пишет N элементов k-ой строки в файл, другая читает. подгруженные в память две строки массива сортируешь по элементам в последовательности: первую по остальным, начиная со второй, вторую по последующим, начиня с третьей, и т.д.

а что такое сортировка по спирали?

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

v_enom, имеется в виду расположить элементы матрицы по спирали? То есть :

да?

Предложу вот что. Во-первых, ессесно, представлять матрицу в виде одномерного массива. Но не просто массива, а эдакого фрагмента ленты машины Тьюринга :  по середине - центральный элемент и ещё слева и справа "видны" k элементов. На эту ленту будем проецировать элементы матрицы в спиральной последовательности. Изначально находимся слева вверху. Сначала читаем 2k+1 элементов матрицы, затем сортируем их, затем самый крайний левый (минимальный) элемент сбрасываем (в выходной массив), а вместо него справа подсасываем в ленту очередной 2k+2-ой элемент, сортируем, ... и поехало.

Поясню на примере приведённой Вами матрицы :



пусть k = 2
1.0) загружаем фрагмент длины 2k+1 = 5 : {1, 8, 7, 6, 9}
1.1) сортируем и получаем : {1, 6, 7, 8, 9}
1.2) сбрасываем в результирующую матрицу крайний левый элемент, а в ленту кладём очередной направо : {6, 7, 8, 9, 2}

2.1) сортируем и получаем : {2, 6, 7, 8, 9}
2.2) {6, 7, 8, 9, 3}

3.1) {3, 6, 7, 8, 9}
3.2) {6, 7, 8, 9, 4}

4.1) {4, 6, 7, 8, 9}
4.2) {6, 7, 8, 9, 5}

5.1) {5, 6, 7, 8, 9}
5.2) элементов справа больше нет. Так что сбрасываем в результат всё, что осталось.

Значение k может оказаться недостаточно большим, чтобы преодолеть "разброс" значений элементов матрицы в один проход. Поэтому, несмотря на то, что в данном примере всё отсортировалось, после пункта 5.2) неплохо бы снова пойти на 1.0), и критерием останова будет то, что за полный проход элементы рассматриваемого фрагмента ни разу не переставлялись (то есть, были уже упорядочены).

Помимо изменения числа k можно поиграться с величиной шага s (количеством элементов сбрасываемых слева/приставляемых справа за один шаг). Чем больше число s, тем сложнее сортировать, но и тем меньше шагов придётся сделать.


Это сообщение отредактировал(а) marcusmae - 11.10.2007, 12:53

Спасибо, akizelokro, я думаю,что примерно также и я придумал сма алгоритм. Приведу пример и объясню в чем пропара, которую сам не знаю как решить.

   (группы по N=2 элемента:   _1___2___3___4__
упорядочить числа массива:   8 7 | 6 5 | 4 3 | 2 1
                                                
допустим бирем первую и 2ю группы:  8 7/ 6 5 , упорядочили внутри каждой из них: 7 8 /  5 6
проверили, равен ли последний элемент первому?  if(FirstGroup[N]==SecondGroup_2[0])
если да, то переставили, получили :   75 /86, отсортировали опять внутри группы и т.д.(рекурсивно), пока не получили:

5 6 / 7 8

потом переходем к группам №2 и 3,      7 8/4 3 , их сортируем, получаем  3 4 / 7 8  и так до конца, пока не получим после первго прохода по циклу вот что:

5 6 / 3 4 / 1 2 / 7 8   

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

по какому критерию мне повторить проход и до каких пор?

Добавлено через 1 минуту и 21 секунду

совершенно точно

marcusmae , тоже спасибо. Хороший способ.
Есть только вопросы:
(я так понял, что вы за основу взяли как бы неотсортированную матрицу (просто  в примере с уже результат после сортировки и упорядочиванию по спирали )

"по середине - центральный элемент и ещё слева и справа "видны" k элементов."
я праивльно понял

  8 3 1 5 2 7 4 6 9    2 - цетральный элемент и слева видно  1,5 и 7, 4 при к=2??
т.е. первый упорядочиваемый массив буедт  1,5,2,7,4 
я правильно понял?



По спирали, я привел пример как представить:

|   1  14  13   12 11 ^
|   2  15   20  19 10  |
|   3  16   17  18  9   |
|   4    5    6    7   8   |
-->----------------------|

Можно использовать твой алгоритм для этого?

Ааа! = Всё, я понял, что такое спираль   Извиняюсь, оказывается, я сделал змейку. Но, не суть : ведь я вообще не описывал, каким образом извлекать элементы матрицы из файла (считал, что это как-то проделывается). Думаю, что будет удобно один раз "раскрутить" спираль в новый файл (каждый раз бегать по элементам строк и столбцов будет проблематично), упорядочить, а потом закрутить обратно.


Можно.



Да. Этот термин ввёл для удобства : поскольку слева всё-время убирается по элементу, а справа - добавляется, то можно считать от центра. Просто термин, он не очень функционален. Эту ленту можно реализовать с помощью стандартного контейнера "Очередь" (LIFO), где last in - последним в очередь становится очередной элемент матрицы (справа), а first out - уходит из очереди сбрасываемый слева. Если знаете о существовании STL, то там есть вполне подходящие Queue и Deque.

Слегка перепутаем элементы :



Возмём k = 3 для разнообразия :

1.0) начальное заполнение очереди : {1, 15, 3, 4, 5, 17, 7}
1.1) сортируем : {1, 3, 4, 5, 7, 15, 17 }
1.2) сбрасываем левый, подгружаем правый : {3, 4, 5, 7, 15, 17, 7}
1.3) результат : -> 1

2.1) {3, 4, 5, 7, 15, 17}
2.2) {4, 5, 7, 15, 17, 11}
2.3) -> 1, 3

3.1) {4, 5, 7, 11, 15, 17}
3.2) {5, 7, 11, 15, 17, 9}
3.3) -> 1, 3, 4

4.1) {5, 7, 9, 11, 15, 17}
4.2) {7, 9, 11, 15, 17, 10}
4.3) -> 1, 3, 4, 5

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

Так? Или я опять чего-то не понял?   

Понятно, большое спасибо.

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

Добавлено через 31 секунду
эх...жаль плюс поставить не могу. мало постов.

Не за что. Желаю успехов   

Не вопрос