Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 00:52

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: *сортировочки
СообщениеДобавлено: Вс окт 30, 2011 20:48 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Написать сортировку:

Код:
\
: sort ( addr u# 'next 'comp 'exchange --> addr u# )

         ;


входные параметры:
addr -- начальный адрес списка (массива)
u# -- количество сортируемых элементов (положительное число от 0 и выше)
'comp ( a1 a2 --> a1 a2 flag) -- адрес метода сравнения двух элементов
'next ( a1 --> a1 a2 | a1 0 ) -- адрес метода перемещения к следующему элементу
'exchange ( a1 a2 --> a2 ) -- адрес метода обмена записей
на выходе адрес первого элемента addr в отсортированном списке а так же количество элементов u#.

При заданном нулевом, единичном, и более количестве элементов сортировка должна быть стабильна. Допустимо создание промежуточных структур данных, однако, сортировка должна быть реентерабельна (то есть параллельный вызов сортировки с другими параметрами не должен нарушать работы другого процесса сортировки). Выбор метода сортировки не ограничивается. Направление сортировки задается методом сравнения comp сортируемых элементов. В качестве сортируемых элементов могут выступать записи произвольной длины в оперативной памяти процесса.



За это сообщение автора mOleg поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 11:11 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
Можно было бы 'next и 'exchange заменить на размер элемента.

Цитата:
Направление сортировки задается методом сравнения comp сортируемых элементов.

Неполная спецификация! как именно задаётся?



За это сообщение автора dynamic-wind поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 13:40 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Неудачная попытка обобщить алгоритмы сортировки путем искусственного выделения базового набора процедур для сортировки.
Вот пример:
Код:
: sort ( a u -- a u ) u! a!  0. m! Im!
  u 0 DO 0xFF is m
         a u + a I + DO I C@ DUP m < IF I is Im is m ELSE DROP THEN LOOP \ найти значение минимума и его адрес
         a I + Im 2\1r2r1w2w                                             \ обменять минимум с начальным элементом
      LOOP a u ;

CREATE arr 12 C, 23 C, 22 C, 44 C, 8 C, 67 C, 41 C, 56 C, 223 C, 111 C, 212 C, 251 C, 211 C, 188 C,

arr 14 sort DUMP
Ps. Сортировка есть, а процедуры 'next 'comp 'exchange явно не выделить по причине нераздельного переплетения кода этих процедур в коде sort.

_________________
С уважением, chess



За это сообщение автора chess поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 13:42 
dynamic-wind писал(а):
Можно было бы 'next и 'exchange заменить на размер элемента.

Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных.

mOleg писал(а):
comp ( a1 a2 --> a1 a2 flag)

flag = -1, если a1 < a2
flag = 0, если a1 = a2
flag = +1, если a1 > a2
Я правильно понял флаг?


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 13:57 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
dynamic-wind писал(а):
Можно было бы 'next и 'exchange заменить на размер элемента.

не стоит.

dynamic-wind писал(а):
Неполная спецификация! как именно задаётся?

'comp ( a1 a2 --> a1 a2 flag)
значением флага flag.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur



За это сообщение автора mOleg поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 13:59 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
white_TigR писал(а):
Я правильно понял флаг?

да

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur



За это сообщение автора mOleg поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 14:00 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
white_TigR писал(а):
Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных.

именно.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur



За это сообщение автора mOleg поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: *сортировочки
СообщениеДобавлено: Пн окт 31, 2011 15:31 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
ладно, поехали:
source file: sort.fts
\ 31.10.2011 ~mOleg
\ Copyright [C] 2011 mOleg mOlegg@ya.ru
\ пример реализации сортировки методом пузырька для конкурса
\ viewtopic.php?p=32468#p32468

memory/ locals.fts

\ сортировка методом обмена
: sort ( addr # | 'i 'c 's --> )
-1 { iterator comparator swapper chg }
BEGIN chg WHILE 0 TO chg
*WHILE 1 - DDUP D>L
BEGIN *WHILE >L
iterator EXECUTE
comparator EXECUTE
IF swapper EXECUTE -1 TO chg
ELSE NIP
THEN
L> 1 -
REPEAT DDROP
DL>
REPEAT
THEN DDROP ;


\! тестовая часть:

\ метод выбора следующего
:> next ( a1 --> a1 a2 | a1 0 ) DUP 1 + ;
\ метод сравнения
:> comp ( a1 a2 --> a1 a2 flag) DDUP B@ SWAP B@ - 0 < ;
\ метод обмена элементов (в данном случае их значений)
:> exch ( a1 a2 --> a2 ) DDUP B@ >R B@ OVER B! R> ROT B! ;

\ исходная строка
: array ( asc # --> ) s" simple sample string" ;

\ тест
: test ( --> )
." исходная строка:" array TYPE CR
array next comp exch sort
." полученная строка:" array TYPE CR
;

пример для форка

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur



За это сообщение автора mOleg поблагодарил: ctrl-C
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB