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!
  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.
Автор:  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
\ 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
       ;

пример для форка
Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/