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

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

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

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

сортировка в лоб маленьких массивов
Подскажите плиз, есть задача: написать программу, которая будет генерировать функции сортировки маленьких(2,3,4 и где-то до 10 элементов) массивов в лоб (например для двух, прога должна содержать один if, для трех, сортировать за три if'a и так далее). Соответственно, сгенерированная программа скорее всего не будет содержать циклов и будет работать только для массивов заданной длины.

Последний раз редактировалось fimadura, 17.11.2007 в 23:34.
  #2  
Старый 18.11.2007, 01:03
гость

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

Как тебе такой вариант: возьми сортировку вставкой и от-unroll'ь циклы для заданного N, т.е.
Код:
if (a[0] < a[1]) swap(a[0], a[1]);
// инвариант: a[0]<=a[1] 
if (a[1] < a[2]) swap(a[1], a[2]);
if (a[0] < a[2]) swap(a[0], a[2]);
// инвариант: a[0]<=a[1]<=a[2]
if (a[2] < a[3]) swap(a[2], a[3]);
if (a[1] < a[3]) swap(a[1], a[3]);
if (a[0] < a[3]) swap(a[0], a[3]);
// инвариант: a[0]<=a[1]<=a[2]<=a[3]
...
  #3  
Старый 18.11.2007, 01:06
гость

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

Извиняюсь, код должен выглядеть так
Код:
if (a[0] > a[1]) swap(a[0], a[1]);
...
if (a[1] > a[2]) swap(a[1], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
...
if (a[2] > a[3]) swap(a[2], a[3]);
if (a[1] > a[2]) swap(a[1], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
...
  #4  
Старый 18.11.2007, 13:46
MBo MBo вне форума
Местный

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

Например, 5 элементов можно отсортировать за 7 сравнений - но это весьма нетривиально (описание есть на этом сайте). Так нужно ли добиваться минимального количества сравнений?

возможно, стоит посмотреть на сортирующие сети.
  #5  
Старый 19.11.2007, 21:00
гость

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

Да нужно именно за 7 сравнений. А ткни плиз в ссылку на сайте. Если сделать unroll какого-нибудь алгоритма, то имхо там получится несколько больше чем nlogn действий (если только это не пирамидальная сортировка). Но хочется чтоб функция сортировки n-элементного массива генерировалась автоматически на этапе компиляции (для заданных n)
  #6  
Старый 20.11.2007, 06:30
MBo MBo вне форума
Местный

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

http://algolist.ru/olimp/sor_prb.php
 


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

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