Jump to content

Photo

Fast Simple Combsort in BASIC


25 replies to this topic

#1 TheBF OFFLINE  

TheBF

    Dragonstomper

  • 638 posts
  • Location:The Great White North

Posted Wed Sep 27, 2017 3:39 PM

A long time ago I came across an article in BYTE magazine (April 1991) about some medical doctors (really) who figured out a great improvement to bubble sort by trial and error.

The COMB sort is similar to the Shell Metzner in that is compares items in the array that are separated by a 'GAP'.

The difference is in how you calculate the GAP.

 

Comb sort uses a magic value of 1.3.  Each time through the array, the GAP is divided by 1.3.

This gives an amazing improvement over BUBBLE sort with only a couple of extra lines of code

And the bigger the array the better the improvement, but even on 32 chars it is 10X faster. :-)

 

I have provided two simple DEMO programs that sort characters on the screen for anyone who might need a sort routine.

 

Bubble sort demo

 

Spoiler

 

 

Spoiler

 



#2 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Thu Sep 28, 2017 12:14 PM

This video sorts 255 chars on the screen.

 

You can really see how each method, COMB, SHELL and Bubble sorting works.

 

At the end you can see how they each perform on the sorted data.

Bubble sort is the fastest on already sorted data, but COMB sort is still good.

Shell Sort not so much on either. :-)

Attached Files



#3 F.G. Kaal OFFLINE  

F.G. Kaal

    Space Invader

  • 38 posts

Posted Fri Jan 12, 2018 11:25 AM

A long time ago ...

 

Interesting story.

I also like the demo programs which are short enough for a little article in our TI magazine "Tijdingen" if it is okay with you.

 

Fred ;-)



#4 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Fri Jan 12, 2018 1:11 PM

 

Interesting story.

I also like the demo programs which are short enough for a little article in our TI magazine "Tijdingen" if it is okay with you.

 

Fred ;-)

 

Ja zeker. 

 

Groeten aan Nederland. :-)



#5 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 9:21 AM

 

Interesting story.

I also like the demo programs which are short enough for a little article in our TI magazine "Tijdingen" if it is okay with you.

 

Fred ;-)

 

Hi Fred,

 

I just realized that you might be in Belgium.  

My apologies if I got it wrong.

 

BF



#6 F.G. Kaal OFFLINE  

F.G. Kaal

    Space Invader

  • 38 posts

Posted Sun Jan 14, 2018 12:07 PM

Hahaha ... no offence, for that matter I could also be from South Africa or Suriname.

But no ... I'm dutch, created in East London, Sout Africa and almost born in London, United Kingdom and almost almost born in Antwerp, Belgium but eventually born in Alkmaar the Netherlands.

 

Made a translation of your post this afternoon inclusive links to this topic and Wikipedea.

 

Fred :P


Edited by F.G. Kaal, Sun Jan 14, 2018 12:12 PM.


#7 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Sun Jan 14, 2018 12:30 PM

Nice!

COMB Sort actually rivals quicksort depending on the order your data is in, and it's easy to implement without recursion.  I think COMB is better in the worst case and Quicksort is better in the best case... or it was the other way around.

I used a variation of COMB in a VB application back in the 90s.
The programmer that wrote some code I inherited didn't know how to implement a sort (!?), and the program that ran nightly required quite a bit of interaction from the night crew so it could use an external sort utility.
So I threw in a sort.  COMB sorted 85,000+ records in about 15 minutes and the program didn't need any interaction once it was kicked off.
FWIW, Bubble sort didn't complete sorting the same data in 12 hours.  I threw that in at first when I couldn't find VB code for quicksort.
I implemented COMB by trying to speed up the code, but I didn't know it was a COMB sort until later.



#8 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 3:43 PM

Hahaha ... no offence, for that matter I could also be from South Africa or Suriname.
But no ... I'm dutch, created in East London, Sout Africa and almost born in London, United Kingdom and almost almost born in Antwerp, Belgium but eventually born in Alkmaar the Netherlands.
 
Made a translation of your post this afternoon inclusive links to this topic and Wikipedea.
 
Fred :P



#9 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 3:45 PM

My wife's family is from Brabant, a couple small villages.
The part of Canada that I live in had thousands of people come here after the war. The land is flat😄

#10 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 3:45 PM

Nice!

COMB Sort actually rivals quicksort depending on the order your data is in, and it's easy to implement without recursion.  I think COMB is better in the worst case and Quicksort is better in the best case... or it was the other way around.

I used a variation of COMB in a VB application back in the 90s.
The programmer that wrote some code I inherited didn't know how to implement a sort (!?), and the program that ran nightly required quite a bit of interaction from the night crew so it could use an external sort utility.
So I threw in a sort.  COMB sorted 85,000+ records in about 15 minutes and the program didn't need any interaction once it was kicked off.
FWIW, Bubble sort didn't complete sorting the same data in 12 hours.  I threw that in at first when I couldn't find VB code for quicksort.
I implemented COMB by trying to speed up the code, but I didn't know it was a COMB sort until later.



#11 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 4:23 PM

Did you discover the 1.3 gap ratio independently?

#12 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Sun Jan 14, 2018 5:00 PM

Did you discover the 1.3 gap ratio independently?

No, as I said, I used a variation.  It's not exactly the same but comb was what I thought it was closest to.  I could be mistaken... wouldn't be the first time.
 

I actually divided the gap by 2 each change and made multiple passes more like bubble sort, but using a for loop that exits if no swaps take place on a pass. 

The for loop executes 1 less time than the amount it was split by. 

The data was split in half at first so 2-1 was the end of the loop at first (for i = 1 to 1), then I divided by half again so 4-1, etc...  

Maybe that's more like some other sort?  
It makes more passes at each level but moves the out of order data further than standard COMB in each pass.  
 



#13 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 6:26 PM

No, as I said, I used a variation.  It's not exactly the same but comb was what I thought it was closest to.  I could be mistaken... wouldn't be the first time.
 

I actually divided the gap by 2 each change and made multiple passes more like bubble sort, but using a for loop that exits if no swaps take place on a pass. 

The for loop executes 1 less time than the amount it was split by. 

The data was split in half at first so 2-1 was the end of the loop at first (for i = 1 to 1), then I divided by half again so 4-1, etc...  

Maybe that's more like some other sort?  
It makes more passes at each level but moves the out of order data further than standard COMB in each pass.  
 

 

I think you found a similar mechanism independently, but with a different GAP ratio.

 

There is another sort called Shell-Metzner or Shellsort that is described here: https://en.wikipedia.../wiki/Shellsort

I think you might have done that.

 

The Combsort is a strange variation that changes the GAP by this magic ratio and it just works well.

https://en.wikipedia.../wiki/Comb_sort

 

I didn't realize until I read the Wikipedia on Shellsort that it is "fair game" to use different GAPs, even using a list of GAPs.

 

All that to say I think you discovered Shellsort.  :)

 

B



#14 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Sun Jan 14, 2018 9:39 PM

 

I think you found a similar mechanism independently, but with a different GAP ratio.

 

There is another sort called Shell-Metzner or Shellsort that is described here: https://en.wikipedia.../wiki/Shellsort

I think you might have done that.

 

The Combsort is a strange variation that changes the GAP by this magic ratio and it just works well.

https://en.wikipedia.../wiki/Comb_sort

 

I didn't realize until I read the Wikipedia on Shellsort that it is "fair game" to use different GAPs, even using a list of GAPs.

 

All that to say I think you discovered Shellsort.  :)

 

B

Shellsort was my 2nd guess... but I thought shellsort was a gapped insertion sort. 
The animations look very different than what my sort does, and it looks much more like comb.
I think the best and worst case are probably the same.
 



#15 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sun Jan 14, 2018 10:45 PM

Shellsort was my 2nd guess... but I thought shellsort was a gapped insertion sort. 
The animations look very different than what my sort does, and it looks much more like comb.
I think the best and worst case are probably the same.
 

 

Do you still have any code lying around?

 

It sounds then like you made the comb sort independently with a  1/2 GAP which works but may be just slightly sub-optimal compared to 1/1.3

 

Pretty cool work by you.



#16 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Mon Jan 15, 2018 12:14 AM

 

Do you still have any code lying around?

 

It sounds then like you made the comb sort independently with a  1/2 GAP which works but may be just slightly sub-optimal compared to 1/1.3

 

Pretty cool work by you.

Code from 1993... ish?  Nope. Not that I know of.

Whether or not it's sub optimal would depend on the data.  Since the GAP doesn't change every pass, it has the potential to move very out of order items really quickly, and anything moved way too far in the initial passes quickly moves back towards it's final location.  
I think it's biggest flaw was the gap change was too large once you got below a certain gap # and there were an excessive number of swaps in the final passes.
It probably should have used a table of GAP values derived from examining the source data.  New data was added, but the order didn't change much from one time to the next.
 


Edited by JamesD, Mon Jan 15, 2018 12:22 AM.


#17 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Mon Jan 15, 2018 7:55 AM

Code from 1993... ish?  Nope. Not that I know of.

Whether or not it's sub optimal would depend on the data.  Since the GAP doesn't change every pass, it has the potential to move very out of order items really quickly, and anything moved way too far in the initial passes quickly moves back towards it's final location.  
I think it's biggest flaw was the gap change was too large once you got below a certain gap # and there were an excessive number of swaps in the final passes.
It probably should have used a table of GAP values derived from examining the source data.  New data was added, but the order didn't change much from one time to the next.
 

 

 

I will have to play with the 1/2 value to see what happens.

I remember in the Byte Magazine article where I found this sort, they showed a graph where these two guys experimented with gap size s and found this magic 1.3 value.  There was a switch as you say when the GAP got below a certain size that they claimed was better but my tests didn't give me an speedup because testing for the condition took more time.

 

So your name needs to go up there in Wikipedia as one of the independent discoverers of this algorithm.



#18 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Mon Jan 15, 2018 10:34 AM

 

 

I will have to play with the 1/2 value to see what happens.

I remember in the Byte Magazine article where I found this sort, they showed a graph where these two guys experimented with gap size s and found this magic 1.3 value.  There was a switch as you say when the GAP got below a certain size that they claimed was better but my tests didn't give me an speedup because testing for the condition took more time.

 

So your name needs to go up there in Wikipedia as one of the independent discoverers of this algorithm.

Well, I was dealing with 85,000+ records with over a hundred added per month.  so the large moves probably made a huge difference.
And remember, my variation used multiple passes like a bubble sort.  

If you have 1000 items and just use 1/2 during the first 4 passes, that should get really out of order data within something like 75 or less distance from it's final location.
If your data is almost in order, you may waste 4 passes... but then that's probably true with the regular comb sort with a data set that size.
Instead of multiple passes like my variation, I think the ideal would use a table of data that follows a curve rather than a linear drop.
I'm sure some math whiz could come up with a theoretical formula you could use but I'm not sure there is a one size fits all formula.
Maybe start with half and then have a multiplier that gradually alters the multiplier. 
It would be interesting to play with.


Edited by JamesD, Mon Jan 15, 2018 10:35 AM.


#19 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Mon Jan 15, 2018 3:40 PM

...

So your name needs to go up there in Wikipedia as one of the independent discoverers of this algorithm.

I didn't catch that until after I posted.

There is a simple rule to getting credit for discovering something.  You have to publish to get credit.
 



#20 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Mon Jan 15, 2018 4:02 PM

I didn't catch that until after I posted.

There is a simple rule to getting credit for discovering something.  You have to publish to get credit.
 

 

Well at least we all know. :-)



#21 JamesD ONLINE  

JamesD

    Quadrunner

  • 8,195 posts
  • Location:Flyover State

Posted Mon Jan 15, 2018 5:24 PM

 

Well at least we all know. :-)



#22 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Tue Jan 23, 2018 4:03 PM

Went down the rabbit hole playing with this combsort and the Dutch Flag Problem.

https://en.wikipedia...al_flag_problem

(no, there is no problem with the Dutch flag)  :)

 

This is not an optimal way to solve it, but it makes an interesting way to view how the sort works.

The sort is using the screen memory as an array of data and sorting in place.

There are 4 different scenarios.  (I apologize that the screen fillers are not all perfect.)

 

I did a version with sprites pointing to where the sort is comparing, but it was too fast and not very helpful.

 

Spoiler

 

 

Attached Files


Edited by TheBF, Tue Jan 23, 2018 4:05 PM.


#23 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Mon Jul 9, 2018 7:36 AM

Update to the Dutch Flag demo. 

 

I have a more complete version on Github now and I took the time to wait for the Bubble sort to finish, for a comparison.

 

The sorted pattern is 11.33 secs with Bubble sort and 11.38 with Comb sort so comparable.

 

All non-sorted input patterns take over 6 minutes with Bubble sort and the Comb sort takes a maximum of 12.5 secs.

 

So if you ever need to sort some data in TI BASIC don't use Bubble sort, use Comb sort which is only a couple of lines bigger.



#24 TheBF OFFLINE  

TheBF

    Dragonstomper

  • Topic Starter
  • 638 posts
  • Location:The Great White North

Posted Sat Jul 28, 2018 7:22 AM

Decompiling Camel Forth

 
Last week I asked the author of Camel Forth, Brad Rodriguez, if he had decompiler code for Camel Forth.
 
He told me he had never written a de-compiler for any Forth that he had written but he was sure "you can handle it". 
So I took a run at it.
 
Forth has a "dictionary" which is a linked list that contains the names of all the words in the language.
Along with the name there are a couple of extra fields that let the system find the code that goes with the word name. 
 
Camel Forth, like FB Forth and Turbo Forth is a "threaded code" system.
This means that the compiler does not generate machine code, but rather creates lists of addresses.
These addresses can point to other routine addresses but eventually they point to real machine code.
So to decompile this kind of Forth means you have to read through each list and find the name of the
word associated with the address, print the name and move ahead two bytes and read the next address.
You continue doing this until you get to the address of the routine called EXIT, which is the Forth
equivalent of "RETURN" or RT in assembler.
 
Each Forth word begins with the address of a machine code routine that is the actual "interpreter" for that kind of word.
There is a special routine for variables, constants, new routine definitions (colon definitions) and one for something
called USER variables that are used when tasks need their own copy of some variables.  These special
routines let you identify the "type" of each Forth word even though Forth is not a "typed" language.
Armed with that "type" information you can figure out how to print out the info for any given Forth word.
 
There are three different "decompilers" in this implementation:
 
One for the "primitves" which are real machine code.
When I encounter a "CODE" word in this decompiler I resorted to simply printing our the machine code since
making a dis-assembler would be a whole other project.  The printed CODE word could actually be pasted
into the CAMEL Forth and used as is so that has some benefit.
 
Another decompiler is for variables, constants and USER variables so you see what there value is.
This is a little bit frivolous because you can do that with the Forth interpreter anytime you want but it makes
the thing consistent for the end user.
 
And a final decompiler is for "colon" definitions. (Forth words)
For some language constructs I elected to show what is compiled in the Forth routine rather than re-creating
the exact source code. This can be a difficult thing for newbies to grok about Forth.
 
The IF ELSE THEN and BEGIN UNTIL words actually compile little code routines called BRANCH and
?BRANCH which are like assembler B @xxx and JEQ @xxxx instructions.  In fact the word BEGIN doesn't
compile anything into a program, It's just a general purpose label for loops to branch back too! So BEGIN
disappears when you decompile Forth code.  The branching words are always followed by a number
which is the how many bytes the program has to jump. Positive numbers jump forward and negative numbers
cause the program to jump back.
 
I also take this approach for ." and DO/LOOP constructs. You see what the compiler did rather than the
de-compiler re-creating pretty source code.
 
The traditional name for a decompiler in Forth is "SEE".
 
Here are the example routines we will de-compile:
*EDIT* Corrected TEST2 per Lee's observation. GIF is still erroneous. Thou hast been warned.
\ Examples to DE-COMPILE

: TEST1  1 2 3 + + . ;

: TEST2  100 0 DO  I .  LOOP ;

: TEST3  BEGIN  ." HELLO WORLD!"  SPACE  AGAIN ;

: TEST4  TEST1 TEST2 TEST3 ;

The de-compiler code is in the spoiler and the GIF shows the decompiler in action.
 
Spoiler

Attached Files


Edited by TheBF, Sat Jul 28, 2018 8:27 AM.


#25 Lee Stewart OFFLINE  

Lee Stewart

    River Patroller

  • 3,700 posts
  • Location:Silver Run, Maryland

Posted Sat Jul 28, 2018 7:36 AM

TEST2 is gonna trash the system with nothing to EMIT on the stack!

 

...lee






0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users