Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 23.11.2010, 15:05
Новичок

Отправить личное сообщение для olegkuzn Посмотреть профиль Найти все сообщения от olegkuzn
 
Регистрация: 16.08.2010
Сообщений: 4

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

Заранее спасибо.
  #2  
Старый 23.11.2010, 15:27
гость

 
Сообщений: n/a

Можно загружать массивы попарно и сортировать их как единое целое: 1 и 2, 1 и 3, ..., 1 и n, 2 и 3, 2 и 4, ..., 2 и n, ..., n-1 и n.
  #3  
Старый 25.11.2010, 18:24
Новичок

Отправить личное сообщение для olegkuzn Посмотреть профиль Найти все сообщения от olegkuzn
 
Регистрация: 16.08.2010
Сообщений: 4

Спасибо за помощь.
Переборка пар массивов - наверное это оптимальное решение.
Пожалуйста помогите решить дополнительную задачу:
1) дано два целочисленных массива A1 и A2
2) необходимо перераспределить элементы этих массивов так, чтобы
любой элемент массива A1 был меньше либо равен любому элементу массива A2.
(Задача в принципе решена обычным перебором каждого элемента массива A1 со всеми элементами A2 но хотелось бы узнать - есть ли более элегантное решение).
Заранее спасибо.
  #4  
Старый 26.11.2010, 10:08
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Можно использовать алгоритм нахождения k-й порядковой статистики (в частности - медианы при равном размере массивов), основанный на таком же разделении (partition), как в QuickSort
http://en.wikipedia.org/wiki/Selection_algorithm
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49
Структура данных. vosminog Вычислительная геометрия 10 05.05.2009 00:49
Структура данных vosminog Сортировка и поиск 3 28.04.2009 14:48
Структура данных. vosminog Математические алгоритмы (другое) 1 28.04.2009 12:59
структура данных BIT гость Задачи 4 12.04.2009 23:27