Comb Sort versus Quick Sort

[SMcNeill]

From my personal experience, I've found quicksort to be generally a little faster than combsort, in most cases.  The issue with quicksort is the limits applied by recursion, which combsort doesn't have.  Generally, I'm never doing anything so time essential that I can't spare an extra second or two, so I just tend to stick to combsort for all my needs, where I never have concerns over stack limits.

[Sanmayce]

@SMcNeill ,
the stack is the least problem, as it is, QB64 is limited to 2-GB of strings, as this benchmark shows.

Unable to sort some 30 million variable-length keys is bad.
Using something like one's own "string descriptor" via MEM could solve the limitation (and the nasty string internal shuffling).
My advice to all QB64 coders is to avoid using strings, use your own structures, QB64' MEM allows using HEAP the way C does.

To me, ignoring this nasty limitation is sign of "640KB are enough" mentality.

For all coders wanting to break free, here is the full C sourcecode of Fastest SORT console tool:
http://www.sanmayce.com/Schmekeriada/index.html
Currently, when the keys exceed Physical RAM, Linux sort is far superior, in future, I have plans to dethrone Linux' sort tool in external sorting as well, my approach is more promising...

@bplus
Won't bother you again.

[bplus]

@Sanmayce sorry if I appeared bothered, your projects are a little over my head but always interesting.

[SMcNeill]

@SMcNeill ,
the stack is the least problem, as it is, QB64 is limited to 2-GB of strings, as this benchmark shows.

Unable to sort some 30 million variable-length keys is bad.
Using something like one's own "string descriptor" via MEM could solve the limitation (and the nasty string internal shuffling).
My advice to all QB64 coders is to avoid using strings, use your own structures, QB64' MEM allows using HEAP the way C does.

To me, ignoring this nasty limitation is sign of "640KB are enough" mentality.

For all coders wanting to break free, here is the full C sourcecode of Fastest SORT console tool:
http://www.sanmayce.com/Schmekeriada/index.html
Currently, when the keys exceed Physical RAM, Linux sort is far superior, in future, I have plans to dethrone Linux' sort tool in external sorting as well, my approach is more promising...

@bplus
Won't bother you again.

There's no limit of 2GB to QB64 programs.  You just need to swap over to working with them directly as _MEM blocks once they reach that size.  See this little demo below and see for yourself:

Code: (Select All)

CONST KB = 1024

CONST MB = KB * 1024

CONST GB = MB * 1024



CONST Limit = 4 * GB

DIM M AS _MEM: M = _MEMNEW(Limit * 4) 'of 16gb in size as I'm filling it with all long values

DIM UL AS _UNSIGNED LONG, R AS _UNSIGNED LONG



$CHECKING:OFF

FOR UL = 0 TO Limit - 1 '-1 for array starting at 0 offset

    _MEMPUT M, M.OFFSET + 4 * UL, UL

NEXT



FOR i = 1 TO 10

    R = 4 * INT(RND * Limit)

    _MEMGET M, M.OFFSET + R, UL

    PRINT UL

NEXT

$CHECKING:ON

Note that the above is creating a 16GB block of memory (4GB of Longs), and it runs with no issues.  On my laptop, the OS only allows it to load 4GB at a time into physical memory, but the rest is loaded into a swapfile, but that's the OS's limits and not something which you're going to have much real control over yourself.

I'd say that's conclusively above any 2GB limit which you might be under the impression that the language has.