Jump to content

Photo

Fast Simple Combsort in BASIC


22 replies to this topic

#1 TheBF OFFLINE  

TheBF

    Dragonstomper

  • 616 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
  • 616 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

  • 32 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
  • 616 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
  • 616 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

  • 32 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,171 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
  • 616 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
  • 616 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
  • 616 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
  • 616 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,171 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
  • 616 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,171 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
  • 616 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,171 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
  • 616 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,171 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,171 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
  • 616 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,171 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
  • 616 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
  • 616 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.






0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users