sort_rc


sort_rc, a C code which can sort a list of any kind of objects, using reverse communication (RC).

The program works by repeatedly asking the user to compare two items on the list. The user is free to carry out the comparison in the calling program, in any desired way.

A typical usage, to sort an array of 100 items, might look something like this:

        n = 100
        indx = 0   -- Indicates the beginning of a sort
 
        begin loop

          sort_rc ( n, &indx, &i, &j, isgn )

          if ( indx < 0 )   (Compare items I and J)

            if ( a[i-1] <= a[j-1] )
              isgn = -1
            else
              isgn = +1
 
           else if ( 0 < indx )  (Swap items I and J)
  
             k      = a[i-1]
             a[i-1] = a[j-1]
             a[j-1] = k
 
           else
 
             break from loop

        end loop
      

The original version of sort_rc() requires the use of several variables declared internally to the function, whose values must be preserved between calls. The conventions for such computations vary from language to language; moreover, this kind of approach means that a single copy of the function cannot handle multiple requests for computation that might arise, especially in parallel computations. For that reason, a revised function, called sort_safe_rc(), is available, which does not rely on hidden internal variables and may safely be used to manage multiple simultaneous sorts.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

sort_rc is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

BACKTRACK_BINARY_RC, a C code which carries out a backtrack search for a set of binary decisions, using reverse communication (RC).

BISECTION_RC, a C code which seeks a solution to the equation F(X)=0 using bisection within a user-supplied change of sign interval [A,B]. The procedure is written using reverse communication (RC).

CG_RC, a C code which implements the conjugate gradient (CG) method for solving a positive definite sparse linear system A*x=b, using reverse communication (RC).

LOCAL_MIN_RC, a C code which finds a local minimum of a scalar function of a scalar variable, without the use of derivative information, using reverse communication (RC), by Richard Brent.

ROOT_RC, a C code which seeks a solution of a scalar nonlinear equation f(x) = 0, or a system of nonlinear equations, using reverse communication (RC), by Gaston Gonnet.

ROOTS_RC, a C code which seeks a solution of a system of nonlinear equations f(x) = 0, using reverse communication (RC), by Gaston Gonnet.

sort_rc_test

SUBSET, a C code which enumerates, generates, randomizes, ranks and unranks combinatorial objects including combinations, compositions, Gray codes, index sets, partitions, permutations, polynomials, subsets, and Young tables. Backtracking routines are included to solve some combinatorial problems.

ZERO_RC, a C code which seeks solutions of a scalar nonlinear equation f(x) = 0, using reverse communication (RC).

Reference:

  1. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.

Source Code:


Last revised on 06 August 2019.