bubble nt a! for @+ @ - + - -if

@ a -1 + a! @ push !+ pop ! then drop next ;

Simple and compact. I was interested to see if such a simple sort could be speeded up without using too many more instructions. I found the Wikipedia entry for Combsort which calculates a decreasing gap between the two comparison values with the aim of getting the smallest values moved into place as quickly as possible.

So I started transliterating the Wiki algorithm into colorForth. The gap is shrunk by a factor of 1.3 which is apparently a result of some extensive testing with varying shrink factors. Initially I wrote a subroutine to multiply by 10 then divide by 13 (plus lots of shuffling registers around):

`shrinkgap`

` a push dup dup or over`

` 10`

` *`

` -13`

` `

`--u/mod`

` pop a! push`

` drop drop drop pop ;`

And then it hit me that 1.3 is only an approximation. There's nothing absolute about it. It occurred to me that if would be much more efficient to use factors of 2 where possible. So my shrink calculator is simply:

2/ dup 2/ +

In other words take (1/2+1/4) (i.e. 0.75) of the gap. 1/1.3 = 0.77 which is amazingly close to 0.75.

In the end my Combsort still took lots of code and only saved a few hundred cycles compared to Chuck's bubblesort.

In the end my Combsort still took lots of code and only saved a few hundred cycles compared to Chuck's bubblesort.

`comb sort`

`,`

`504`

` node`

` 0`

` org`

`,`

`4`

` ,`

` 19`

` ,`

` 7`

` ,`

` 1`

` ,`

` 12`

` ,`

` 13`

` ,`

` 0`

` ,`

,`11`

` ,`

` 3`

` ,`

` 9`

` ,`

`,`

`17`

` ,`

` 16`

` ,`

` 13`

` ,`

` 6`

` ,`

,`2`

` ,`

` 1ffff`

` ,`

` 5`

` ,`

`,`

`shrink`

` 11`

` 2/ dup 2/ + if ;`

` then - 2* - ;`

comb

` tn`

` push dup dup`

`,`

...

`begin`

`,`

......

`16`

` pop dup push a!`

`,`

......

`dup or`

` swpd`

` push`

`,`

......

`shrink`

`,`

......

`over over - . +`

`,`

......

`for dup a + b!`

`,`

......

`@ -`

` 1`

` + @b + -if`

`,`

......

`gt`

` 20`

` @ @b ! !b pop pop`

`,`

......

`dup or - push push`

`,`

......

`le`

` then drop @+ drop next`

`,`

...

`26`

` dup dup dup or - +`

`,`

......

`if dup or - then`

` gap1?`

`,`

......

`pop`

` swpd?`

`,`

......

`over - and or -`

`,`

...

`until pop ;`

`,`

`2e`

` 17 0`

` comb`

` 32`

` r---`

## No comments:

Post a Comment