'*****************************************************
'* Calculate the median value of an array with the   *
'* Heapsort Method                                   *
'* ------------------------------------------------- *
'* REFERENCE:                                        *
'* "NUMERICAL RECIPES By W.H. Press, B.P. Flannery,  *
'*  S.A. Teukolsky and W.T. Vetterling, Cambridge    *
'*  University Press, 1986" [BIBLI 08].              *
'*                                                   *
'*                      Basic Version By J-P Moreau  *
'*                           (www.jpmoreau.fr)       *
'* ------------------------------------------------- *
'* SAMPLE RUN:                                       *
'*                                                   *
'* Table to be sorted:                               *
'*                                                   *
'*  925  518  215  447  948  405   23  886  809  398 *
'*  195  651  451  251  477   78  389  472  774  291 *
'*  942  885  157  143  623   57  183  766  576  888 *
'*   22  145  143  903  128  398  938   58  426  674 *
'*   32   88  269  845  104  711  628  417  671  226 *
'*  266  324  763  298  871  538  639  991  386  652 *
'*  408  331   19  874  680  952  672   92  576  624 *
'*  760  936  735  712  676   14  163  847  367  731 *
'*                                                   *
'*  Median Value: 474.5                              *
'*                                                   *
'*  Sorted table (Heapsort method):                  *
'*                                                   *
'*   14   19   22   23   32   57   58   78   88   92 *
'*  104  128  143  143  145  157  163  183  195  215 *
'*  226  251  266  269  291  298  324  331  367  386 *
'*  389  398  398  405  408  417  426  447  451  472 *
'*  477  518  538  576  576  623  624  628  639  651 *
'*  652  671  672  674  676  680  711  712  731  735 *
'*  760  763  766  774  809  845  847  871  874  885 *
'*  886  888  903  925  936  938  942  948  952  991 *
'*                                                   *
'*****************************************************
DEFINT I-N

DIM A(100)      'Table to be sorted

  CLS
  N = 80'initialize size of table
  TMAXVALUE = 1000

  'initialize random generator
  RANDOMIZE TIMER

  'generate random table of numbers (from 0 to TMAXVALUE)
  FOR i = 1 TO N
    A(i) = TMAXVALUE * RND(1)
  NEXT i

  PRINT
  PRINT " Table to be sorted:"
  GOSUB 2000 'call TWRIT(N,A)

  'call MDIAN subroutine
  GOSUB 1500 'call MDIAN(A,N,AMED)

  PRINT
  PRINT " Median Value: "; AMED

  PRINT : PRINT
  PRINT " Sorted table (Heapsort method):"
  GOSUB 2000 'call TWRIT(N,A)

  PRINT

END

'*****************************************************
'*   Sorts an array A of length N in ascending order *
'*                by the Heapsort method             *
'* ------------------------------------------------- *
'* INPUTS:                                           *
'*         N      size of table A                    *
'*         A      table to be sorted                 *
'* OUTPUT:                                           *
'*         A      table sorted in ascending order    *
'*                                                   *
'* NOTE: The Heapsort method is a N Log2 N routine,  *
'*       and can be used for very large arrays.      *
'*****************************************************
1000 'Subroutine HPSORT(N, A)
'Labels: 10, 20

  L = N / 2 + 1
  IR = N
  'The index L will be decremented from its initial value during the
  '"hiring" (heap creation) phase. Once it reaches 1, the index IR
  'will be decremented from its initial value down to 1 during the
  '"retirement-and-promotion" (heap selection) phase.
10 IF L > 1 THEN
    L = L - 1
    RRA = A(L)
  ELSE
    RRA = A(IR)
    A(IR) = A(1)
    IR = IR - 1
    IF IR = 1 THEN
      A(1) = RRA
      RETURN
    END IF
  END IF
  i = L
  J = L + L
20 IF J <= IR THEN
    IF J < IR THEN
      IF A(J) < A(J + 1) THEN J = J + 1
    END IF
    IF RRA < A(J) THEN
      A(i) = A(J)
      i = J: J = J + J
    ELSE
      J = IR + 1
    END IF
    GOTO 20
  END IF
  A(i) = RRA
  GOTO 10

END

'*******************************************************
'* Given an array A of N numbers, returns their median *
'* value AMED. The array A is modified and returned    *
'* sorted in ascending order.                          *
'*******************************************************
1500 'Subroutine MDIAN(A, N, AMED)
'N2:Integer

  GOSUB 1000  'call HPSORT(N,A)
  N2 = N / 2
  IF 2 * N2 = N THEN
    AMED = .5 * (A(N2) + A(N2 + 1))
  ELSE
    AMED = A(N2 + 1)
  END IF
RETURN

'write table of size N to standard output
2000 'SUBROUTINE TWRIT(N,A)
  F$ = " ####"
  PRINT
  FOR i = 1 TO N
    PRINT USING F$; A(i);
    IF INT(i / 10) = i / 10 THEN PRINT
  NEXT i
RETURN

'end of file tmdian.bas