Fast Simple Combsort in BASIC

[+TheBF]

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

[JamesD]

I threw together a version of the sort I mentioned for a test program.
You can find the code on my blog.
https://jdiffendaffer.blogspot.com/2018/11/string-variable-testsort-code-basic.html

[+TheBF]

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.

[JamesD]

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

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.

[+TheBF]

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

 

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.

[JamesD]

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

 

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 November 18, 2018 by JamesD

[JamesD]

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

[+TheBF]

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.

[+Lee Stewart]

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

[+TheBF]

 

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

 

...lee

 

Thanks

[JamesD]

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

[+TheBF]

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 November 21, 2018 by TheBF