• Sorting Procedures

    From Gary Scott@21:1/5 to All on Tue Nov 16 10:47:30 2021
    Some compilers provide a convenient sort procedure that works with
    multiple data types and sizes, usually quicksort. I've not seen other potentially faster algorithms provided however, e.g. radix sort. Is
    that because its harder to make it generally applicable or because
    quicksort is "good enough"?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From gah4@21:1/5 to Gary Scott on Tue Nov 16 16:13:12 2021
    On Tuesday, November 16, 2021 at 8:47:33 AM UTC-8, Gary Scott wrote:
    Some compilers provide a convenient sort procedure that works with
    multiple data types and sizes, usually quicksort. I've not seen other potentially faster algorithms provided however, e.g. radix sort. Is
    that because its harder to make it generally applicable or because
    quicksort is "good enough"?

    C has a library routine named qsort, but there is no requirement that it implement
    quicksort, other than both start with q. Plain quicksort has the problem that an
    already sorted list is worst case. There are fixes that are usually implemented.

    Java sort routines use merge sort, as it is stable and quicksort isn't.

    I did once, mostly to see if it could be done, write the routine to call C's qsort from Fortran, though not trying for the most general case.

    General sort routines generally use a user-supplied comparison
    routine that compares two items. Radix sort doesn't work with comparisons,
    so is hard to use for problems like that. Radix sort has some specific
    uses, but a general purpose sort algorithm is not one of them.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Robin Vowels@21:1/5 to Gary Scott on Wed Nov 17 02:38:23 2021
    On Wednesday, November 17, 2021 at 3:47:33 AM UTC+11, Gary Scott wrote:
    Some compilers provide a convenient sort procedure that works with
    multiple data types and sizes, usually quicksort. I've not seen other potentially faster algorithms provided however, e.g. radix sort. Is
    that because its harder to make it generally applicable or because
    quicksort is "good enough"?

    Have a look at R.P. Rich's comprehensive book on sorting methods:
    "Sorting Methods illustrated with PL/I programs."
    It includes run times with various quantities of data.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Duffy@21:1/5 to Gary Scott on Wed Nov 17 22:44:32 2021
    Gary Scott <garylscott@sbcglobal.net> wrote:
    Some compilers provide a convenient sort procedure that works with
    multiple data types and sizes, usually quicksort. I've not seen other potentially faster algorithms provided however, e.g. radix sort. Is
    that because its harder to make it generally applicable or because
    quicksort is "good enough"?

    The Fortran Standard Library proposals include

    https://stdlib.fortran-lang.org/module/stdlib_sorting.html

    eg "ORD_SORT is a hybrid stable comparison algorithm combining merge
    sort, and insertion sort" and "introsort is a hybrid unstable comparison algorithm combining quicksort, insertion sort, and heap sort".

    Cheers, David Duffy

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Gary Scott@21:1/5 to David Duffy on Wed Nov 17 17:41:53 2021
    On 11/17/2021 4:44 PM, David Duffy wrote:
    Gary Scott <garylscott@sbcglobal.net> wrote:
    Some compilers provide a convenient sort procedure that works with
    multiple data types and sizes, usually quicksort. I've not seen other
    potentially faster algorithms provided however, e.g. radix sort. Is
    that because its harder to make it generally applicable or because
    quicksort is "good enough"?

    The Fortran Standard Library proposals include

    https://stdlib.fortran-lang.org/module/stdlib_sorting.html

    eg "ORD_SORT is a hybrid stable comparison algorithm combining merge
    sort, and insertion sort" and "introsort is a hybrid unstable comparison algorithm combining quicksort, insertion sort, and heap sort".

    Cheers, David Duffy

    Cool. My most recent project must sort massive (GB) arrays associated
    with its ("row") categories. To do this, I used a combination of quick
    sort and bubble sort (for different components) and assigning indices to various numerical components to speed up the copy processes (rather than searching for a character string match). Some of these standard library options may have saved me some headaches. But what I did would not have otherwise created an acceptably responsive GUI had I not gone to some
    extreme measures (including massive algorithm tuning efforts (e.g.
    swapping array indices and rearranging data structures). I'm surprised
    I was able to get all this data to fit in a commodity work PC and give
    near real time graphing performance that no other application came close to.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)