Next: 7.8 Implementation aids Up: 7 Internal programs Prev: 7.6 Matrix and vector manipulations Contents

7.7 Sorting and dichotomy

Numerous sorting subroutines  are proposed here. They differ in the type and number of input parameters. They all have "HEAP" in their names except BUBBLE. The *HEAP* subroutines correspond to sorts of O(log n), whereas BUBBLE is of O(n**2).

•       SUBROUTINE BUBBLE(TAB,N)
        INTEGER N,TAB(N)
  

  sorts TAB in  order of increasing values (BUBBLE-SORT).

•       SUBROUTINE HEAP(CRITER, RECORD, N)
        INTEGER N, RECORD(N)
        REAL CRITER(N)
  

  sorts   the values of CRITER in increasing order. RECORD follows the reordering.

•       SUBROUTINE HEAP2I(CRITER, N)
        INTEGER N
        INTEGER CRITER(2, N)
  

  Sorts   the values of CRITER(1, *) in increasing order. CRITER(2, *) follows the reordering.

•       SUBROUTINE HEAP3I(CRITER, N)
        INTEGER N
        INTEGER CRITER(3, N)
  

  sorts the values  of CRITER(1, *) in increasing order. CRITER(2, *) and CRITER(3, *) follows the reordering.

•       SUBROUTINE HPD2I(CRITER, RECORD, N)
        INTEGER N, RECORD(2, N)
        DOUBLE PRECISION CRITER(N)
  

  sorts the values   of CRITER in increasing order. RECORD follows the reordering.

•       SUBROUTINE HEAPDI(CRITER, RECORD, N)
        INTEGER N, RECORD(N)
        DOUBLE PRECISION CRITER(N)
  

  sorts the values   of CRITER in increasing order. RECORD follows the reordering.

•       SUBROUTINE HEAPI(CRITER, N)
        INTEGER N
        INTEGER CRITER(N)
  

  sorts the values of  CRITER in increasing order.

•       SUBROUTINE HEAPI2(CRITER, RECORD, N)
        INTEGER N, RECORD(N)
        INTEGER CRITER(N)
  

  sorts the values of   CRITER in increasing order. RECORD follows the reordering.

•       SUBROUTINE HEPI2I(CRITER, RECORD, N)
        INTEGER N, RECORD(2, N)
        INTEGER CRITER(N)
  

  sorts the  values of CRITER in increasing order. RECORD follows the reordering.

•       SUBROUTINE HEAPI3(CRITER, RECRD1, RECRD2, RECRD3, N)
        INTEGER N
        INTEGER RECRD1(N), RECRD2(N), RECRD3(N)
        INTEGER CRITER(N)
  

  sorts the  values of CRITER in increasing order. RECRD* follows the reordering.

•       SUBROUTINE DHEAP(CRITER,RECORD,N)
        INTEGER N,RECORD(N)
        DOUBLE PRECISION CRITER(N)
  

  sorts the  values of CRITER in increasing order. RECORD follows the reordering.

•       SUBROUTINE HPLX2I(CRITER, N)
        INTEGER N
        INTEGER CRITER(2, N)
  

  lexicographically sorts the values  of CRITER(1, *) and CRITER(2, *) in increasing order.

•       SUBROUTINE HPLX2R(CRITER, RECORD, N)
        INTEGER N
        REAL CRITER(2, N)
        INTEGER RECORD(N)
  

  lexicographically sorts the values  of CRITER(1, *) and CRITER(2, *) in increasing order.

•       SUBROUTINE HPLXNI(CRITER, MM, N)
        INTEGER N, MM
        INTEGER CRITER(MM, N)
  

  lexicographically sorts the values  of CRITER(1, *), CRITER(2, *) ... CRITER(MM, *) in increasing order.

•       SUBROUTINE HPLXNR(CRITER, MM, N)
        INTEGER N, MM
        REAL CRITER(MM, N)
  

  lexicographically sorts the values  of CRITER(1, *), CRITER(2, *) ... CRITER(MM, *) in increasing order.

•       INTEGER FUNCTION IDICHO(CRIT, N, VAL)
        INTEGER N
        INTEGER CRIT(N), VAL
  

  searches for value  VAL in CRIT by dichotomy . CRIT is assumed to be sorted in increasing order.
  

  Input: CRIT, N, VAL
  

  Output: IDICHO = Index in CRIT if VAL is found;

  if VAL < CRIT(1);

  N if VAL > CRIT(N).
  

  The following relation holds:

  CRIT(IDICHO(CRIT, N, VAL)) VAL < CRIT(IDICHO(CRIT, N, VAL)+1)

•       INTEGER FUNCTION DICHO(CRIT, N, VAL)
        INTEGER N
        REAL CRIT(N), VAL
  

  searches for value VAL  in CRIT by dichotomy.

  CRIT is assumed to be sorted in increasing order.
  

  Input: CRIT, N, VAL
  

  Output: DICHO = index in CRIT if VAL is found;

  if VAL < CRIT(1);

  N if VAL > CRIT(N).
  

  The following relation holds:

  CRIT(DICHO(CRIT, N, VAL)) VAL < CRIT(DICHO(CRIT, N, VAL)+1)