Jump to content

Photo

Fast Simple Combsort in BASIC


36 replies to this topic

#26 TheBF OFFLINE  

TheBF

    Dragonstomper

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

Posted Sat Jul 28, 2018 7:41 AM

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

 

...lee

 

LOL.  You are right again.  I didn't run the code examples.  :)

 

Back to work...

 

B



#27 JamesD OFFLINE  

JamesD

    Quadrunner

  • 8,267 posts
  • Location:Flyover State

Posted Fri Nov 16, 2018 10:36 PM

I threw together a version of the sort I mentioned for a test program.
You can find the code on my blog.
https://jdiffendaffe...code-basic.html



#28 TheBF OFFLINE  

TheBF

    Dragonstomper

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

Posted Sat Nov 17, 2018 8:31 AM

Cool!!

 

The 12hr runtime with no completion that you mention really shows the problems with Bubble sorting large numbers of records.

Exponential expansion at its finest.

 

I should do a comparison of your gap value of 2 versus 1.3 that comb sort recommends.

I have some demo code that should make that pretty simple.  I will publish results here when I get something.



#29 JamesD OFFLINE  

JamesD

    Quadrunner

  • 8,267 posts
  • Location:Flyover State

Posted Sat Nov 17, 2018 9:18 AM

FWIW, the C++ version of that software took about 5 minutes. 
The quicksort helped a little, but the language made a huge difference..  :D

Bubble sort sucks because doesn't move data very far per pass. 
My version moves it as far as possible thanks to the gap. 
Small mods to the loops could make it function exactly like comb sort.
If I calculate the maximum number of passes where data can be swapped at each level, I could eliminate passes where no swaps take place.
That's the Q loop. Just change the start value, the step to -1, and change Q to zero if no swaps take place. 
An else would do that last part, but regular basic on the MC-10 doesn't have ELSE.
But what is the theoretical number of passes? 
I was going to try N-1  (divide # in list by 2 and you use 1, by 4 and you use 3, 8 & 7, etc...) but the first attempt was messed up, so I cleaned up the loops and left that for another day.

This is one of those tasks people started running and came back later. 
I should time how long each pass takes.  
For a 0.89 MHz machine to sort 850+ names that are often very similar in 10 minutes... I'd say that's acceptable.  
If I ditch the data I'm not using, I could probably fit all 1000 names in that array.
 



#30 TheBF OFFLINE  

TheBF

    Dragonstomper

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

Posted Sat Nov 17, 2018 11:23 AM

So I have an onscreen sort of the Dutch flag problem, I just pulled up the numbers in the source code

 

         RNDSCREEN  START COMBSORT STOP.  WAIT  \ 00:12.28
         RNDSCREEN  START BUBBLE        STOP. WAIT  \  06:00.15   :-D 

 

When I replaced the  /1.35 with divide by 2 (which is very fast in forth because it's one shift instruction)

 

The sort was fast out of the gate, but quickly degenerated to a bubble sort because the GAP became 1.

 

This made the results very dependant on input data.

To convert a Russian flag (BLUE WHITE RED) to a Dutch flag (RED WHITE BLUE) it was only 7.5 secs

 

But when the input was random red,white and blue characters it took 3 mins, 51 seconds.

 

 So it looks like a fractional GAP of GAP=GAP/1.3  is generally better than GAP=GAP/2  but not for all cases.
 



#31 JamesD OFFLINE  

JamesD

    Quadrunner

  • 8,267 posts
  • Location:Flyover State

Posted Sat Nov 17, 2018 5:33 PM

So I have an onscreen sort of the Dutch flag problem, I just pulled up the numbers in the source code

 

         RNDSCREEN  START COMBSORT STOP.  WAIT  \ 00:12.28
         RNDSCREEN  START BUBBLE        STOP. WAIT  \  06:00.15   :-D

 

When I replaced the  /1.35 with divide by 2 (which is very fast in forth because it's one shift instruction)

 

The sort was fast out of the gate, but quickly degenerated to a bubble sort because the GAP became 1.

 

This made the results very dependant on input data.

To convert a Russian flag (BLUE WHITE RED) to a Dutch flag (RED WHITE BLUE) it was only 7.5 secs

 

But when the input was random red,white and blue characters it took 3 mins, 51 seconds.

 

 So it looks like a fractional GAP of GAP=GAP/1.3  is generally better than GAP=GAP/2  but not for all cases.
 

I haven't tried 1.3, but I tried 1.7 which was faster than 2, and starting with a larger gap than dividing by 2 may be a little faster for out of order data..  
Without eliminating the last pass at each gap, it has no chance of being faster than the comb sort, and even then it's probably not as fast.
It's more of an optimized bubbles sort, and I'm going to make a few other tests to see if a hunch is true.
*edit*
1.7 Was faster than 1.3 by quite a bit, but 1.5 seems to be faster than 1.7.

*edit*
1.5 is faster than 1.4 and 1.6... at least with my data.
*edit*
After some additional testing, 30+% of all passes through the data were a waste, and calculating a theoretical maximum number of passes is useless.
It's about as optimized as it can get.  Also, the optimization that reduces the number of items compared in a pass rarely does much before the final pass on my data.


Edited by JamesD, Sat Nov 17, 2018 7:40 PM.


#32 JamesD OFFLINE  

JamesD

    Quadrunner

  • 8,267 posts
  • Location:Flyover State

Posted Sun Nov 18, 2018 12:18 PM

See my latest reply to that post on my blog.  Now I remember why I thought it was a comb sort.
 



#33 TheBF OFFLINE  

TheBF

    Dragonstomper

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

Posted Tue Nov 20, 2018 7:02 AM

See my latest reply to that post on my blog.  Now I remember why I thought it was a comb sort.
 

 

 

How do I find your BLOG? A search for JamesD didn't find it.



#34 Lee Stewart OFFLINE  

Lee Stewart

    River Patroller

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

Posted Tue Nov 20, 2018 7:29 AM

How do I find your BLOG? A search for JamesD didn't find it.

 

Looks like he put a link to it back in post #27.

 

...lee



#35 TheBF OFFLINE  

TheBF

    Dragonstomper

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

Posted Tue Nov 20, 2018 12:19 PM

 

Looks like he put a link to it back in post #27.

 

...lee

 

Thanks



#36 JamesD OFFLINE  

JamesD

    Quadrunner

  • 8,267 posts
  • Location:Flyover State

Posted Tue Nov 20, 2018 7:15 PM

Sorry to send you to my blog like that.  It was just getting tedious posting in several places.



#37 TheBF OFFLINE  

TheBF

    Dragonstomper

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

Posted Tue Nov 20, 2018 8:25 PM

Sorry to send you to my blog like that.  It was just getting tedious posting in several places.

 

No worries.  I assumed it was an Atariage blog and went looking.  


Edited by TheBF, Tue Nov 20, 2018 8:25 PM.





0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users