*сортировочки

mOleg

Написать сортировку:

Код:

\ 
: 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

Можно было бы 'next и 'exchange заменить на размер элемента.

Цитата:

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

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

chess

Неудачная попытка обобщить алгоритмы сортировки путем искусственного выделения базового набора процедур для сортировки.
Вот пример:

Код:

: 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

dynamic-wind писал(а):

Можно было бы 'next и 'exchange заменить на размер элемента.

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

mOleg писал(а):

comp ( a1 a2 --> a1 a2 flag)

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

mOleg

dynamic-wind писал(а):

Можно было бы 'next и 'exchange заменить на размер элемента.

не стоит.

dynamic-wind писал(а):

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

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

mOleg

white_TigR писал(а):

Я правильно понял флаг?

да

mOleg

white_TigR писал(а):

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

именно.

mOleg

ладно, поехали:

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
       ;

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

*сортировочки

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