Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 19:36

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - *сортировочки
Автор Сообщение
  Заголовок сообщения:  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
;

пример для форка
Сообщение Добавлено: Пн окт 31, 2011 15:31
  Заголовок сообщения:  Re: *сортировочки  Ответить с цитатой
white_TigR писал(а):
Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных.

именно.
Сообщение Добавлено: Пн окт 31, 2011 14:00
  Заголовок сообщения:  Re: *сортировочки  Ответить с цитатой
white_TigR писал(а):
Я правильно понял флаг?

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

не стоит.

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

'comp ( a1 a2 --> a1 a2 flag)
значением флага flag.
Сообщение Добавлено: Пн окт 31, 2011 13:57
  Заголовок сообщения:  Re: *сортировочки  Ответить с цитатой
dynamic-wind писал(а):
Можно было бы 'next и 'exchange заменить на размер элемента.

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

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

flag = -1, если a1 < a2
flag = 0, если a1 = a2
flag = +1, если a1 > a2
Я правильно понял флаг?
Сообщение Добавлено: Пн окт 31, 2011 13:42
  Заголовок сообщения:  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.
Сообщение Добавлено: Пн окт 31, 2011 13:40
  Заголовок сообщения:  Re: *сортировочки  Ответить с цитатой
Можно было бы 'next и 'exchange заменить на размер элемента.

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

Неполная спецификация! как именно задаётся?
Сообщение Добавлено: Пн окт 31, 2011 11:11
  Заголовок сообщения:  *сортировочки  Ответить с цитатой
Написать сортировку:

Код:
\
: 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 сортируемых элементов. В качестве сортируемых элементов могут выступать записи произвольной длины в оперативной памяти процесса.
Сообщение Добавлено: Вс окт 30, 2011 20:48

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


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