Sort Routines

[johnno56]

I find the youtube videos of sorting visualisation fascinating... Then I remembered the old quickbasic sort demo. Ran it 'as is'. Two annoying points. All sort routines completed in zero seconds and the associated sound was a mega earache... lol

For those who are curious: http://galileo.phys.virginia.edu/classes/551.jvn.fall01/SORTS.BAS

I added a '_limit 5' to each sort routine... so as to slow it down... and commented out the sound commands...

  [ You are not allowed to view this attachment ]  

I would like to know if QB64 is capable of reproducing the youtube sort demo visualisations?
Example:

[CharlieJV]

That is right fascinating.  Thanks !

[OldMoses]

Been looking for some examples of various sort routines. Hard to find them in QBASIC dialects. That'll be useful. Thanks for posting.

[SMcNeill]

Been looking for some examples of various sort routines. Hard to find them in QBASIC dialects. That'll be useful. Thanks for posting.

I'm just curious:  Do you guys ever search the forums for anything you might be interested in??

https://qb64forum.alephc.xyz/index.php?topic=530.msg5451#msg5451

'Date tested O()     Algorithm name                                                                 time(ms)  in-place  deployment special notes
'2018-Mar-13 N       FlashSort (CGSortLibArr() AS DOUBLE, start AS LONG, finish AS LONG, order&)         117  N         requires inversion for descending order
 
'2018 Mar 13 NLogN   QuickSortRecursive (CGSortLibArr() AS DOUBLE, start&, finish&, order&)              148  Y         Requires CPU stack, uses middle array element for
'                                                                                                                       partitioning step.
 
'2018 Mar 13 NLogN   QSortRecursiveSimplified (CGSortLibArr() AS DOUBLE, start&, finish&)                160  Y         Requires CPU stack
 
'2018nMar 13 NLogN   QuickSortIterativeMedianOf3 (CGSortLibArr() AS DOUBLE, Start&, Finish&, order&)     161  Y         Uses software-based stack, Median of Three
'                                                                                                                       Partitioning strategy used to defeat "QuickSort
'                                                                                                                       Killer" array arrangements for QuickSort algorithms
'                                                                                                                       using the middle element as the sole pivot chice.
'                                                                                                                       Remember, DDoS attacks using this flaw in Java?
 
'2018 Mar 13 NLogN   QuickSortIterative (CGSortLibArr() AS DOUBLE, Start&, Finish&, order&)              164  Y         Uses software-based stack, handy for old CPUs that do
'                                                                                                                       not support recursive stacks in hardware. Or just to
'                                                                                                                       implement for certainty where hardware or virtualization
'                                                                                                                       is not guaranteed to support hardware stacks.
'
 
'2018 Mar 13 N       HashListSort (CGSortLibArr() AS DOUBLE, start AS LONG, Finish AS LONG, order&)      171  N         Can be implemented without CGSortLibArr() with mods
'                                                                                                                       With the data type and range in this original demo
'                                                                                                                       HashListSort actually BEATS FlashSort by at least
'                                                                                                                       an 11% margin. Don't let this fool you. This is the
'                                                                                                                       result of a SINGLE run, and generalizing on a single
'                                                                                                                       run is not a good idea, which is why I assembled a
'                                                                                                                       test harness using multiple passes and ascending,
'                                                                                                                       descending order.
 
'2018 Mar 13 NLogN   IntroSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                       226  N         uses MergeSort, HeapSort, InsertionSort and performs
'                                                                                                                       comparably and favorably to non-hybrid QuickSort,
'                                                                                                                       usually within a few percent or less.
 
'2018 Mar 13 NLogN   QuickSortDualPivot (CGSortLibArr() AS DOUBLE, start&, finish&, order&)              244  Y         Not bulletproof but works for most cases of highly
'                                                                                                                       repetitive data fails for low-repetition data.
 
'2018 Mar 13 NLongN  SnakeSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                       250  N         Auxiliary memory is O(N). Also a very nice-performing
'                                                                                                                       algorithm. Not the fastest (yes, compared to HashListSort
'                                                                                                                       with 70ms @ (0, 131071) elements, not even FlashSort can
'                                                                                                                       keep up.
 
'2018 Mar 13 NLogN   MergeSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                       257  N         Auxiliary memory is O(N/2) when used with
'                                                                                                                       EfficientMerge
 
'2018 Mar 13 NLogN   MergeSortTwoWay (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                 287  N         Good for memory-constrained systems
 
'2018 Mar 13 N       RadixSort (a() AS DOUBLE, start&, finish&, order&)                                  296  N         Only for integers, otherwise it will use MergeSort
'                                                                                                                       to maintain RadixSort's stability
 
'2018 Mar 14         BucketSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&, recurse%)            280  N         Without recursion, 100 times slower 20812ns
'                                                                                                                       Final subarray sort done with MergeSort keeps this
'                                                                                                                       algorithm competitive.
 
'2018 Mar 13         SinglePassShellSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)             335  Y         Got this idea from reading LOTS of articles. Performs
'                                                                                                                       respectably.
 
'2018 Mar 13         PrimeGapSort2 (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                   343  Y         Invented by CodeGuy/Zom-B, uses wheel factorization
'                                                                                                                       to generate primes.
 
'2018 Mar 13         PostSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                        351  N         Large auxiliary overhead. Final sort of subarrays
'                                                                                                                       done with MergeSort also keeps this algorithm competitive
'                                                                                                                       Like BucketSort, except that it uses a fixed number of
'                                                                                                                       buckets. Using fewwer actually increases speed, at 1
'                                                                                                                       Bucket, it's essentially a MergeSort.
 
'2018 Mar 13         PrimeGapSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                    382  Y         Invented by CodeGuy. Proud to declare PrimeGapSort
'                                                                                                                       is competitive and performs on par with ShellSort or
'                                                                                                                       better. Uses gaps that are prime.
 
'2018 Mar 13         JoinSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                        484  N         A respectably quick algorithm. Also, not the fastest
'                                                                                                                       but for a comparison sort, good enough.
 
'2018 Mar 13 NLogN   HeapSort (CGSortLibArr() AS DOUBLE, Start&, Finish&, order&)                        492  Y
 
'2018 Mar 13         ShellSortMetzner (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                500  Y         With this variant, it is appreciably faster than ShellSort.
 
'2018-Mar-13         ShellSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                       546  Y
 
'2018 Mar 13         CombSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                        898  Y
 
'2018 Mar 13 Nlog^2N BatcherOddEvenMergeSort (CGSortLibArr() AS DOUBLE, Start&, Finish&)                1093  Y         Only works for power-of-2 sized arrays
 
'2018 Mar 13         SmoothSort (TypedCGSortLibArr() AS DataElement, order&)                            1292  Y         requires use of TYPE array) and only 0 to ubound.
'                                                                                                                       no ranges
'2018-Mar 13         ShellSortBidirectional (CGSortLibArr() AS DOUBLE, start&, finish&, order&)         2421  Y
 
'2018 Mar 13         BitonicSort (CGSortLibArr() AS DOUBLE, lo&, n&, dir&)                              2609  Y
 
'2018-Mar-13 N^2     InsertionSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                229133  Y         Very fast for nearly-sorted arrays. Used as finishing
'                                                                                                                       run for many ShellSort variations.
 
'2018 Mar 13 N^2     InsertionSortBinary (CGSortLibArr() AS DOUBLE, start&, finish&, order&)          330328  Y         Supposedly faster than InsertionSort. Using randomized
'                                                                                                                       Double-precision, generally non-repeating, not proven
'                                                                                                                       in practice.
 
'2018 Mar 13 N^2     CycleSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                    784852  Y
 
'            N^2     bubblesort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                      ------
'            N^2     CocktailSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                    ------
'            N^2     SelectionSort (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                   ------
'            N^2     InsertionSortx (CGSortLibArr() AS DOUBLE, start&, finish&, order&)                  ------
'                    FlashSORTType (CGSortLibArr() AS FlashRec, start AS LONG, finish AS LONG, order&)   ------ as yet untested. An experimental algorithm for use with
'                                                                                                       string-type variables
 
'* InsertionSort(), BubbleSort(), MergeSort() are considered stable. The remainder either are not or as yet unconfirmed
'* I ran these individually and corrected flaws. Sorts that have times have been tested in ascending/descending order
'* this is a work in progress. The algorithms marked by ------ are too slow to be practical for this demo code
'* Tested on double-precision data.

[johnno56]

Steve,

I am fully aware of the sort routines on this site. What I was interested in was the 'graphical representations' of the sort routines and not the sort routines themselves. The old sortdemo.bas seems to manipulate strings to display the sorting. I am interested in whether or not QB64 can replicate the graphics of the youtube videos. Because I have no idea as to how that is done.

When you referred to "you guys ever search", I have to understand that you were referring to 'me', as the other 'guys' were merely responding to my request. The fault is mine not theirs. It's ok to say "do 'you' ever search". I would accept that as constructive criticism... lol

I do appreciate and thank you for all the effort you have made in pointing out the routines.

Regards

J

[SMcNeill]

My "you" was directed more in general towards everyone on the site here.  We have a ton of stuff on the forums here, and yet a lot of times we see things like what OldMoses mentioned: "Been looking for some examples of various sort routines. Hard to find them in QBASIC dialects..."  And yet, the forum here has a ton of sort routines written in QB64 Basic.

My question was directed as an enquiry about whether people use search, or not.  If not, I'm curious as to why not.  Is the search system too difficult to navigate?  Does it not give the results?  Are the search terms too difficult to sort through?  If people aren't searching for things they're interested in, why aren't they?

[johnno56]

Understood. Probably me being too precise... lol  I cannot speak on behalf of the others, but my search regime, is usually F1 within the IDE, Forum and Wiki. (If there was a 'hard copy' of 'help' I would use that as well... old habits)

If I have caused offence by raising the issue, I apologise, my intent was not to do so...

[Dimster]

I find search is a great tool Steve but it has it's limitations. If you don't use the exact words to search for I wind up with either an overwhelming amount of stuff to look through or have missed the one article/thread/illustration that I could have used. Search also needs you to devote time, some times lots of time. We can't save the search criteria either. Some times I do a search for the same kind of thing but phrased it slightly different.

For some of these very common topics, like a search for sorting algorythms, I'd like to see exactly what you have laid out here in one topic in our library or learning section. By the way, I have learnt the best search criteria is generally the name of one our very talented codes. Makes for great reading.

[OldMoses]

I often execute forum searches that come up with nothing. Even when I know many of the search terms, or distinctly remember seeing a thread, it seems to not find the things that I know damn well are there. Then there is the picking out every instance of a word and filling the search with junk, as in "I've been out of sorts lately", or "can I get some help sorting out a bug?" At that point I might just as well go thread by thread, and life's not in endless supply. As Dimster said "it has its limitations". So when those things happen, and my patience with it ends, I go out into the general net and find mostly C++ code, which I still find incomprehensible.

This was a nice little package, that was in one place, which I appreciated and said so. I've lately been trying to wrap my meager brain limitations around a sorting problem. It was not my intention to offend, but I have no control over what others find offensive.

[SMcNeill]

@OldMoses You weren't offensive, and I wasn't offended.  Allow me to apologize if it somehow sounded like I was. 

I've never had any issues with finding things relevant to what I was looking for using search, and as such, I was curious why others might have difficulty making use of it.  By nature, I like to teach and help others learn things.  Unfortunately, it's rather difficult to help teach people anything, if you don't know where they're having difficulties with a subject and what they might need help with.  From the way it sounds, it seems as if everyone who is having problem with search is having the issues from getting back too many results to sort through them.  Let me share a few quick tips which I use for searching:

Step 1: I often choose the simplest of search terms to begin with.  In this case, let's just choose "sort" for a single word match, rather than trying to expand to "sorting", "sorting routines", or anything else.

Step 2:  Usually, I leave the user field blank for my first run at searching for what I want.  Now, I know certain members are more proficient with certain things than others (bplus has a ton of graphic routines, petr does a lot of sound manipulation, fellippe is the inform guy, and so on), but I usually don't limit by user unless I get 17 pages of results to dig through to look for something of relevance.

Step 3: Normally, when I do searching, I set the search order to "by most recent topic first".  QB64 is an evolving language.  We add functionality all the time.  The way we do things in 2022 may be quite different and easier than how we did them in 2016.  People write code, then they expand upon it, or they do bug corrections for it.  I've found that most of the time, searching for most recent topics gives me the best results.  We're all learning as we live and grow, and the things we started out learning and coding 5 years ago as we got interested in a subject, are no where near as impressive as what we're doing today.  Go for the new stuff first, in my experience!

Step 4: And this is the biggie, I think:  Check the option for, "Search in topic subjects only".  You'll ignore those posts with the comments like, "I've been out of sorts lately," and "can I get help sorting out a bug?"  What you're limiting the search tool to is topics which start with "SORT" in the title.

Click search, and in this case, you get back a grand total of 15 results to glance through, and it's obvious when scrolling the page of results that codeguy has a very long topic with a ton of "SORT" in it.  You can also see that the title of his post is " CodeGuy Standard Sorting Library (Because QB64 dot net happens)"...   

If you're looking for sort routines, a "Standard Sorting Library" seems to me like it'd be an excellent place to start for examples and such, and it'd probably be a good place to check out to help learn about the subject in question.


Limit your searches to the titles only, and you can eliminate a lot of the wheat from the chaff.  Look for keywords in the titles, which showcase that someone was wanting to show/teach/share something rather than ask about something.  "Library", "Demo", "Example", and so on, are often great indicators that somebody has gone into depth with a subject to explain something, rather than just someone asking about something.

If I can't find any titles which stand out as being most useful, then I go back and check for those that seem questioning.  If someone had the same question I have, if somebody posted a solution to their issue, it might be the same solution I need for my current issue.


And ^  those are the basic steps I use when trying to search for something, and normally I don't have any problem locating what I'm looking for with the forum search tool.

[MasterGy]

I use a "lossy" but very fast queuing for 3d rendering.
Good for whole numbers. For example, if I know that the numbers will be between 0 and 1000, I create an array dim x (1000), load the indexes where they need to, and then read them out in sequence for-next. It is unprofitable because if a value close to 2 goes into 1 account, the latter will overwrite the former. (I think they're in the old dos games when a texture sometimes flashes because that's how sorting was used)