Stdlib: Implement sorting algorithms

[certik]

At the very least there needs to be some quick algorithm for sorting integers and reals. But I think we can implement several algorithms and the user can choose.

This will also be needed to implement #38.

[jvdp1]

Is it also an option to link to the algorithms provided by BLAS/LAPACK?

[certik]

@jvdp1 I think so. We'll need to depend on Lapack for #10 anyway.

[certik]

Here are inefficient implementations from fortran-utils: https://github.com/certik/fortran-utils/blob/b43bd24cd421509a5bc6d3b9c3eeae8ce856ed88/src/sorting.f90, the API however might be useful to get inspiration from. Here is more efficient implementation of quicksort: https://github.com/certik/hfsolver/blob/b4c50c1979fb7e468b1852b144ba756f5a51788d/src/sorting.f90#L165. I think there will be much better implementations out there, including in Lapack.

[jvdp1]

Here is a mutli-threaded one:
https://balsoftware.net/index.php/open-source/multi-thread-sort/
Not sure what is the license.

[rweed]

The following routines implement the version of quicksort outlined in Hanson's and Hopkins book and on the associated web site (http://www.siam.org/books/ot134). The publishers license is very permissive (at least as I read it). This version supports REAL32, REAL64, INT8, INT16, INT32, INT64, Character strings and arrays, and a user defined type. Unfortunately, the file tool for this page does not know anything about .f90 or .F90 file extensions. Here is the code:

Main quicksort module: type specific routines are overloaded with generic qsort interface. Sorting can be in place or return a integer permutation array leaving original array untouched. Sorting can be in either ascending or descending order.

quickSort.F90.txt

A base user class that can be extended to define user specific classes. Specifies dummy methods for relational operators needed for sorting etc, a print method and an assignment method.

userClass.F90.txt

A test program that tests sorting integers, reals, characters, and a user point class that is sorted on distance (Euclidean Norm)

testqsort.f90.txt

The point class used in test program. It is extended from the base User class

point.f90.txt

[jacobwilliams]

Here are some of mine:

• https://github.com/jacobwilliams/fortran-search-and-sort
• https://github.com/jacobwilliams/stringsort (see also here about natural sorting of strings).

[ivan-pi]

A few more:

Sorting routines in various libraries

• ACM
  
  
  
  • Algorithm 402 (version linked here is part of CLAWPACK)
  
  
• HSL
  
  
  
  • KB07
  
  
• IBM Engineering and Scientific Subroutine Library (ESSL)
  
  
  
  • ISORT, SSORT, and DSORT
  
  
  • ISORTX, SSORTX, and DSORTX
  
  
  • ISORTS, SSORTS, and DSORTS
  
  
• IMSL
  
  
  
  • SORT_REAL
  
  
  • SVRGN
  
  
  • SVRGP
  
  
  • SVIGN
  
  
  • SVIGP
  
  
  • SVRBN
  
  
  • SVRBP
  
  
  • SVIBN
  
  
  • SVIBP
  
  
• LAPACK
  
  
  
  • slasrt
  
  
  • dlasrt
  
  
• NAG
  
  
  
  • Searching and sorting
  
  
• Numerical Recipes
• ORDERPACK
• SLATEC (search for the routines ipsort, isort, spsort, ssort, dpsort, dsort, and hpsort)

Various user routines

• Sorting in Fortran by Michael Rutter
• sorting programs in Fortran by Jean-Pierre Moreau
• Sorting by John Mahaffy
• FORTRAN Bubble Sort Speghetti Code by Thomas W Bennet
• MULTI-THREADED SORT by Bal Software
• quicksort by Tim Hoar
• lcpsort - Module for sorting and merging ASCII text strings by N. Shamsundar, University of Houston (a C version by the same author is provided here)
• qsort_inline by Joseph M. Krahn at FortranWiki
• Coding Fortran: a sorting module by Michael Wirth
• Parsing and Sorting with Fortran by Mike Rourke
• quicksort by @t-nissie and a modified version by @1AdAstra1
• Selection sort by C.-K. Shene
• LexicalSort by unknown author from comp.lang.fortran newsgroup
• Ancora sul sort di ‘Compilati vs. Interpretati’ – 2; blog post comparing various Fortran sort implementations (in Italian!)
• M_sort by @urbanjost
• simple_fortran_argsort by @Astrokiwi
• Bubble Sort (WikiBooks)
• Gnome sort (Rosetta Code)
• Insertion sort (Rosetta Code)

Internet forums and discussion boards

• ordering function in Fortran (comp.lang.fortran)
• Reverse quick sort in Fortran (StackExchange)
• Sorting an array from lowest to greatest FORTRAN (StackExchange)
• Fortran Bubble Sort Algorithm (StackExchange)
• Open-source version of Intel Fortran sort routines (StackExchange) provided by Rafik Zurob

Interfaces to C qsort

• Oracle
• Intel Fortran

Published works

• Books
  
  
  
  • Algorithms and Data Structures in F and Fortran by Robin Vowels (see chapter 1)
  
  
  • Introduction to Programming with Fortran by Ian Chivers and Jane Sleightholme (see pp. 703-732)
  
  
  • Fortran 90 & 95 Array and Pointer Techniques (eBook) by Loren P. Meissner (see chapters 2 and 3)
  
  
• Articles
  
  
  
  • Transferable FORTRAN Subroutine for Rapid Extended Sorting
  
  
  • Technical Note: Efficient sorting routines in FORTRAN 77