Forth http://fforum.winglion.ru/ |
|
*сортировочки http://fforum.winglion.ru/viewtopic.php?f=19&t=2772 |
Страница 1 из 1 |
Автор: | mOleg [ Вс окт 30, 2011 20:48 ] |
Заголовок сообщения: | *сортировочки |
Написать сортировку: Код: \ : 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 сортируемых элементов. В качестве сортируемых элементов могут выступать записи произвольной длины в оперативной памяти процесса. |
Автор: | dynamic-wind [ Пн окт 31, 2011 11:11 ] |
Заголовок сообщения: | Re: *сортировочки |
Можно было бы 'next и 'exchange заменить на размер элемента. Цитата: Направление сортировки задается методом сравнения comp сортируемых элементов. Неполная спецификация! как именно задаётся? |
Автор: | chess [ Пн окт 31, 2011 13:40 ] |
Заголовок сообщения: | Re: *сортировочки |
Неудачная попытка обобщить алгоритмы сортировки путем искусственного выделения базового набора процедур для сортировки. Вот пример: Код: : sort ( a u -- a u ) u! a! 0. m! Im! Ps. Сортировка есть, а процедуры 'next 'comp 'exchange явно не выделить по причине нераздельного переплетения кода этих процедур в коде sort.
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 |
Автор: | white_TigR [ Пн окт 31, 2011 13:42 ] |
Заголовок сообщения: | Re: *сортировочки |
dynamic-wind писал(а): Можно было бы 'next и 'exchange заменить на размер элемента. Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных. mOleg писал(а): comp ( a1 a2 --> a1 a2 flag) flag = -1, если a1 < a2 flag = 0, если a1 = a2 flag = +1, если a1 > a2 Я правильно понял флаг? |
Автор: | mOleg [ Пн окт 31, 2011 13:57 ] |
Заголовок сообщения: | Re: *сортировочки |
dynamic-wind писал(а): Можно было бы 'next и 'exchange заменить на размер элемента. не стоит. dynamic-wind писал(а): Неполная спецификация! как именно задаётся? 'comp ( a1 a2 --> a1 a2 flag) значением флага flag. |
Автор: | mOleg [ Пн окт 31, 2011 13:59 ] |
Заголовок сообщения: | Re: *сортировочки |
white_TigR писал(а): Я правильно понял флаг? да |
Автор: | mOleg [ Пн окт 31, 2011 14:00 ] |
Заголовок сообщения: | Re: *сортировочки |
white_TigR писал(а): Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных. именно. |
Автор: | mOleg [ Пн окт 31, 2011 15:31 ] |
Заголовок сообщения: | Re: *сортировочки |
ладно, поехали: source file: sort.fts пример для форка |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |