Автор |
Сообщение |
|
|
Заголовок сообщения: |
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 ;
пример для форка
ладно, поехали: [pre]source file: sort.fts [b][color=#C0C0C0]\ 31.10.2011 ~mOleg[/color] [color=#C0C0C0]\ Copyright [C] 2011 mOleg mOlegg@ya.ru[/color] [color=#C0C0C0]\ пример реализации сортировки методом пузырька для конкурса[/color] [color=#C0C0C0]\ http://fforum.winglion.ru/viewtopic.php?p=32468#p32468[/color]
[color=#00F000]memory/ locals.fts[/color]
[color=#C0C0C0]\ сортировка методом обмена[/color] [color=#FF8000]: sort[/color] [color=#0080C0]( addr # | 'i 'c 's --> )[/color] [color=#00F000]-1[/color] { iterator comparator swapper chg } [color=#00A0A0]BEGIN[/color] chg [color=#00A0A0]WHILE[/color] [color=#00F000]0[/color] TO chg [color=#00A0A0]*WHILE[/color] [color=#00F000]1[/color] - DDUP D>L [color=#00A0A0]BEGIN[/color] [color=#00A0A0]*WHILE[/color] >L iterator [color=#C00000]EXECUTE[/color] comparator [color=#C00000]EXECUTE[/color] [color=#00A0A0]IF[/color] swapper [color=#C00000]EXECUTE[/color] [color=#00F000]-1[/color] TO chg [color=#00A0A0]ELSE[/color] NIP [color=#00A0A0]THEN[/color] L> [color=#00F000]1[/color] - [color=#00A0A0]REPEAT[/color] DDROP DL> [color=#00A0A0]REPEAT[/color] [color=#00A0A0]THEN[/color] DDROP [color=#FF8000];[/color]
[color=#0080C0]\! тестовая часть:[/color]
[color=#C0C0C0]\ метод выбора следующего[/color] [color=#FF8000]:> next[/color] [color=#0080C0]( a1 --> a1 a2 | a1 0 )[/color] DUP [color=#00F000]1[/color] + [color=#FF8000];[/color] [color=#C0C0C0]\ метод сравнения[/color] [color=#FF8000]:> comp[/color] [color=#0080C0]( a1 a2 --> a1 a2 flag)[/color] DDUP B@ SWAP B@ - [color=#00F000]0[/color] < [color=#FF8000];[/color] [color=#C0C0C0]\ метод обмена элементов (в данном случае их значений)[/color] [color=#FF8000]:> exch[/color] [color=#0080C0]( a1 a2 --> a2 )[/color] DDUP B@ >R B@ OVER B! R> ROT B! [color=#FF8000];[/color]
[color=#C0C0C0]\ исходная строка[/color] [color=#FF8000]: array[/color] [color=#0080C0]( asc # --> )[/color] [color=#00F000]s" simple sample string"[/color] [color=#FF8000];[/color]
[color=#C0C0C0]\ тест[/color] [color=#FF8000]: test[/color] [color=#0080C0]( --> )[/color] [color=#00F000]." исходная строка:"[/color] array TYPE CR array next comp exch sort [color=#00F000]." полученная строка:"[/color] array TYPE CR [color=#FF8000];[/color] [/b][/pre] пример для [url=http://fforum.winglion.ru/viewtopic.php?p=30814#p30814]форка[/url]
|
|
|
|
Добавлено: Пн окт 31, 2011 15:31 |
|
|
|
|
|
Заголовок сообщения: |
Re: *сортировочки |
|
|
white_TigR писал(а): Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных. именно.
[quote="white_TigR"]Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных.[/quote] именно.
|
|
|
|
Добавлено: Пн окт 31, 2011 14:00 |
|
|
|
|
|
Заголовок сообщения: |
Re: *сортировочки |
|
|
white_TigR писал(а): Я правильно понял флаг? да
[quote="white_TigR"]Я правильно понял флаг?[/quote] да
|
|
|
|
Добавлено: Пн окт 31, 2011 13:59 |
|
|
|
|
|
Заголовок сообщения: |
Re: *сортировочки |
|
|
dynamic-wind писал(а): Можно было бы 'next и 'exchange заменить на размер элемента. не стоит. dynamic-wind писал(а): Неполная спецификация! как именно задаётся? 'comp ( a1 a2 --> a1 a2 flag) значением флага flag.
[quote="dynamic-wind"]Можно было бы 'next и 'exchange заменить на размер элемента.[/quote] не стоит.
[quote="dynamic-wind"]Неполная спецификация! как именно задаётся?[/quote] '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 Я правильно понял флаг?
[quote="dynamic-wind"]Можно было бы 'next и 'exchange заменить на размер элемента.[/quote] Не написано, что сортируется массив. Там может быть и связный список в качестве входных данных.
[quote="mOleg"]comp ( a1 a2 --> a1 a2 flag)[/quote] 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.
Неудачная попытка обобщить алгоритмы сортировки путем искусственного выделения базового набора процедур для сортировки. Вот пример: [code]: 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 [/code]Ps. Сортировка есть, а процедуры 'next 'comp 'exchange явно не выделить по причине нераздельного переплетения кода этих процедур в коде sort.
|
|
|
|
Добавлено: Пн окт 31, 2011 13:40 |
|
|
|
|
|
Заголовок сообщения: |
Re: *сортировочки |
|
|
Можно было бы 'next и 'exchange заменить на размер элемента. Цитата: Направление сортировки задается методом сравнения comp сортируемых элементов. Неполная спецификация! как именно задаётся?
Можно было бы 'next и 'exchange заменить на размер элемента.
[quote]Направление сортировки задается методом сравнения comp сортируемых элементов.[/quote] Неполная спецификация! как именно задаётся?
|
|
|
|
Добавлено: Пн окт 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 сортируемых элементов. В качестве сортируемых элементов могут выступать записи произвольной длины в оперативной памяти процесса.
Написать сортировку:
[code]\ : sort ( addr u# 'next 'comp 'exchange --> addr u# )
;[/code]
входные параметры: 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 |
|
|
|
|