Jump to content

Photo

Fast Simple Combsort in BASIC


1 reply to this topic

#1 TheBF OFFLINE  

TheBF

    Moonsweeper

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

    Moonsweeper

  • Topic Starter
  • 321 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






0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users