'*****************************************************
'*     Sorting 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 *
'*                                                   *
'*  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 sorting subroutine
  gosub 1000 'call HPSORT(N,A)

  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


'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 sort3.bas